Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Kocay’s lemma, Whitney’s theorem, and some polynomial invariant reconstruction problems. | Kocay s lemma Whitney s theorem and some polynomial invariant reconstruction problems Bhalchandra D. Thatte Allan Wilson Centre for Molecular Ecology and Evolution and Institute of Fundamental Sciences Massey University Palmerston North New Zealand Submitted Jun 29 2004 Accepted Nov 7 2005 Published Nov 25 2005 Mathematics Subject Classifications 05C50 05C60 Abstract Given a graph G an incidence matrix N G is defined on the set of distinct isomorphism types of induced subgraphs of G. It is proved that Ulam s conjecture is true if and only if the N-matrix is a complete graph invariant. Several invariants of a graph are then shown to be reconstructible from its N-matrix. The invariants include the characteristic polynomial the rank polynomial the number of spanning trees and the number of hamiltonian cycles in a graph. These results are stronger than the original results of Tutte in the sense that actual subgraphs are not used. It is also proved that the characteristic polynomial of a graph with minimum degree 1 can be computed from the characteristic polynomials of all its induced proper subgraphs. The ideas in Kocay s lemma play a crucial role in most proofs. Kocay s lemma is used to prove Whitney s subgraph expansion theorem in a simple manner. The reconstructibility of the characteristic polynomial is then demonstrated as a direct consequence of Whitney s theorem as formulated here. 1 Introduction Suppose we are given the collection of induced subgraphs of a graph. There is a natural partial order on this collection defined by the induced subgraph relationship between members of the collection. An incidence matrix may be constructed to represent this relationship along with the multiplicities with which members of the collection appear as induced subgraphs of other members. Given such a matrix is it possible to construct the graph or compute some of its invariants Such a question is motivated by the treatment of chromatic polynomials in .
