An algebraic formulation of the graph reconstruction conjecture

DOI10.1002/JGT.21880zbMATH Open1333.05207arXiv1301.4121OpenAlexW2172023833WikidataQ122940086 ScholiaQ122940086MaRDI QIDQ2800593FDOQ2800593

Authors: Igor C. Oliveira, Bhalchandra D. Thatte 

Publication date: 15 April 2016

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

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)$.

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

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

zbMATH Keywords

graph reconstruction conjecture

Mathematics Subject Classification ID

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

Cites Work

• The falsity of the reconstruction conjecture for tournaments
• A congruence theorem for trees
• Almost every graph has reconstruction number three
• A census of non-reconstructable digraphs. I: Six related families
• Title not available (Why is that?)
• Title not available (Why is that?)
• The \(k\)-orbit reconstruction and the orbit algebra
• On the reconstruction of planar graphs

Cited In (11)

• The reconstruction conjecture and edge ideals
• Graph reconstruction and quantum statistical mechanics
• Title not available (Why is that?)
• Title not available (Why is that?)
• The converse of Kelly's lemma and control-classes in graph reconstruction
• A conjecture on the reconstruction of graphs from metric balls of their vertices
• Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphs
• Reconstructing graphs from a deck of all distinct cards
• Title not available (Why is that?)
• Reconstructibility of the \(K_r\)-count from \(n - 1\) cards
• Kocay's lemma, Whitney's theorem, and some polynomial invariant reconstruction problems

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)