An Algebraic Formulation of the Graph Reconstruction Conjecture
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 be the number of distinct mutually nonisomorphic graphs on n vertices, and let be the number of distinct decks that can be constructed from these graphs. Then the difference 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 . 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 . In particular, all n-vertex graphs are reconstructible if one such matrix has rank . 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 .
References
[1]
M.Bilinski, Y. S.Kwon, and X.Yu, On the reconstruction of planar graphs. J. Combin. Theory, Ser. B Volume 97 Issue 5 2007, pp.745-756.
[2]
B.Bollobás, Almost every graph has reconstruction number three. J. Graph Theory Volume 14 Issue 1 1990, pp.1-4.
[3]
J. A.Bondy, A graph reconstructor's manual. In: Surveys in Combinatorics, 1991 Guildford, 1991, Vol. 166 of Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge, 1991, pp. pp.221-252.
[4]
P. J.Kelly, On isometric transformations. PhD thesis, University of Wisconsin-Madison, 1942.
[5]
P. J.Kelly, A congruence theorem for trees. Pacific J. Math. Volume 7 Issue 1 1957, pp.961-968.
[6]
W. L.Kocay, An extension of Kelly's lemma to spanning subgraphs, Proceedings of the Tenth Manitoba Conference on Numerical Mathematics and Computing, Vol. II Winnipeg, Man., 1980, vol. Volume 31, 1981, pp. pp.109-120.
[7]
W. L.Kocay, Some new methods in reconstruction theory. Combinatorial Mathematics IX, Springer, Berlin, 1982, pp. pp.89-114.
[8]
B. D.McKay, Small graphs are reconstructible. Australas J. Combin. Volume 15 1997, pp.123-126.
[9]
V. B.Mnukhin, On reconstruction of graph polynomials. In Proceedings of the 27 Int. Wiss. Kolloq., Ilmenau, 25-29 Okt, 1982, pp. pp.87-90.
[10]
V. B.Mnukhin, The k-orbit reconstruction and the orbit algebra, Acta Applicandae Math. Volume 29 Issue 1-2 1992, pp.83-117.
[11]
P. K.Stockmeyer, The falsity of the reconstruction conjecture for tournaments, J Graph Theory Volume 1 Issue 1 1977, pp.19-25.
[12]
P. K.Stockmeyer, A census of nonreconstructible digraphs. I. Six related families, J Combin Theory Ser B Volume 31 Issue 2 1981, pp.232-239.
[13]
W. T.Tutte, Graph Theory as I Have Known It. Oxford University Press, Oxford, 1998.
[14]
S. M.Ulam, A Collection of Mathematical Problems. Interscience Tracts in Pure and Applied Mathematics, no. 8. Interscience Publishers, New York-London, 1960.
[15]
D. B.West, Introduction to Graph Theory. Prentice Hall, 2001.
- An Algebraic Formulation of the Graph Reconstruction Conjecture
Recommendations
A counterexample to the pseudo 2-factor isomorphic graph conjecture
A graph G is pseudo 2-factor isomorphic if the parity of the number of cycles in a 2-factor is the same for all 2-factors of G. Abreu etal. conjectured that K3,3, the Heawood graph and the Pappus graph are the only essentially 4-edge-connected pseudo 2-...
The graph formulation of the union-closed sets conjecture
The union-closed sets conjecture asserts that in a finite non-trivial union-closed family of sets there has to be an element that belongs to at least half the sets. We show that this is equivalent to the conjecture that in a finite non-trivial graph ...
Hadwiger's Conjecture and inflations of the Petersen graph
An inflation of a graph G is obtained by replacing vertices in G by disjoint cliques and adding all possible edges between any pair of cliques corresponding to adjacent vertices in G . We prove that the chromatic number of an arbitrary inflation F of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
John Wiley & Sons, Inc.
United States
Publication History
Published: 01 April 2016
Author Tag
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Feb 2025