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

zbMATH Open1081.05077arXivmath/0507375MaRDI QIDQ2583663FDOQ2583663

Authors: Bhalchandra D. Thatte 

Publication date: 17 January 2006

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/math/0507375

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• An algebraic formulation of the graph reconstruction conjecture
• On the reconstruction of graph invariants
• Graph characterising polynomials
• The characteristic polynomial of a graph is reconstructible from the characteristic polynomials of its vertex-deleted subgraphs and their complements
• On the reconstruction of the characteristic polynomial of a graph

zbMATH Keywords

characteristic polynomialsreconstructibilityisomorphism typesUlam's conjecture

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cited In (3)

• Title not available (Why is that?)
• Graph characterising polynomials
• Title not available (Why is that?)

This page was built for publication: Kocay's lemma, Whitney's theorem, and some polynomial invariant reconstruction problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2583663)