Kocay's lemma, Whitney's theorem, and some polynomial invariant reconstruction problems

Details Kocay's lemma, Whitney's theorem, and some polynomial invariant reconstruction problems Kocay's lemma, Whitney's theorem, and some polynomial invariant reconstruction problems

2005-07-18

arxiv.org/abs/math/0507375v2

The Electronic Journal of Combinatorics 12 (2005), #R63.

Mathematics

Combinatorics

31 pages

Scientific paper

Given a graph G, an incidence matrix N(G) is defined for the set of distinct isomorphism types of induced subgraphs of G. If Ulam's conjecture is true, then every graph invariant must be reconstructible from this matrix, even when the graphs indexing the rows and the columns of N(G) are unspecified. It is proved that the characteristic polynomial, the rank polynomial, and the number of spanning trees of a graph are reconstructible from its N-matrix. 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. Here 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.

Affiliated with

Also associated with

No associations

Rating

Kocay's lemma, Whitney's theorem, and some polynomial invariant reconstruction problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Kocay's lemma, Whitney's theorem, and some polynomial invariant reconstruction problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kocay's lemma, Whitney's theorem, and some polynomial invariant reconstruction problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-287758