An algebraic formulation of the graph reconstruction conjecture

DOI10.1002/JGT.21880MaRDI QIDQ2800593zbMATH OpenOpenAlexWikidataFDO

Authors Igor C. Oliveira, Bhalchandra D. Thatte

Publication date 15 April 2016

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.4121, http://wrap.warwick.ac.uk/129325/1/WRAP-algebraic-formulation-graph-reconstruction-conjecture-Oliveira-2015.pdf

zbMATH Keywords

graph reconstruction conjecture

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: The graph reconstruction conjecture asserts that every finite simple graph on at least three vertices can be reconstructed up to isomorphism from its deck - the collection of its vertex-deleted subgraphs. Kocay's Lemma is an important tool in graph reconstruction. Roughly speaking, given the deck of a graph $G$ and any finite sequence of graphs, it gives a linear constraint that every reconstruction of $G$ must satisfy. Let $psi(n)$ be the number of distinct (mutually non-isomorphic) graphs on $n$ vertices, and let $d(n)$ be the number of distinct decks that can be constructed from these graphs. Then the difference $psi(n)-d(n)$ measures how many graphs cannot be reconstructed from their decks. In particular, the graph reconstruction conjecture is true for $n$-vertex graphs if and only if $psi(n)=d(n)$. We give a framework based on Kocay's lemma to study this discrepancy. We prove that if $M$ is a matrix of covering numbers of graphs by sequences of graphs, then $d(n)geqmathsf{rank}_{m}athbbR(M)$. In particular, all $n$-vertex graphs are reconstructible if one such matrix has rank $psi(n)$. To complement this result, we prove that it is possible to choose a family of sequences of graphs such that the corresponding matrix $M$ of covering numbers satisfies $d(n)=mathsf{rank}_{m}athbbR(M)$.

Recommendations

• scientific article; zbMATH DE number 3906536
• Graph reconstruction -- some new developments
• Reconstructing graphs from a deck of all distinct cards
• The reconstruction conjecture and edge ideals
• Progress on the reconstruction conjecture

Cites work

• A census of non-reconstructable digraphs. I: Six related families
• A congruence theorem for trees
• Almost every graph has reconstruction number three
• scientific article; zbMATH DE number 1051281 (Why is no real title available?)
• scientific article; zbMATH DE number 1151365 (Why is no real title available?)
• On the reconstruction of planar graphs
• The k-orbit reconstruction and the orbit algebra
• The falsity of the reconstruction conjecture for tournaments

Cited in

(11)

• A conjecture on the reconstruction of graphs from metric balls of their vertices
• Kocay's lemma, Whitney's theorem, and some polynomial invariant reconstruction problems
• The converse of Kelly's lemma and control-classes in graph reconstruction
• scientific article; zbMATH DE number 5287238 (Why is no real title available?)
• scientific article; zbMATH DE number 3906536 (Why is no real title available?)
• scientific article; zbMATH DE number 4023330 (Why is no real title available?)
• Graph reconstruction and quantum statistical mechanics
• Reconstructing graphs from a deck of all distinct cards
• Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphs
• Reconstructibility of the K_r-count from n - 1 cards
• The reconstruction conjecture and edge ideals

This page was built for publication: An algebraic formulation of the graph reconstruction conjecture

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