The converse of Kelly’s lemma and control-classes in graph reconstruction. (English) Zbl 1086.05051

Let \(G\) be a graph on \(n\) vertices. Kelly’s lemma in graph reconstruction states that, from the deck of vertex-deleted subgraphs of \(G\), the number \(\binom{G}{H}\) of subgraphs of \(G\) isomorphic to \(H\) can be determined for all graphs \(H\) of order less than \(n\). The authors here prove the converse of this lemma and some variations. Therefore the reconstruction conjecture can be stated as follows: if all the \(\binom{G}{H}\), for \(| V(H)| <n\), are known, then this determines \(G\) uniquely. This motivates some ways of strenghtening the conjecture. For example, if \(\mathcal K\) is a class of graphs and \(\binom{G}{H}\) is given for all graphs \(H\) in \(\mathcal K\) and \(| V(H)| <n\), does this determine \(G\) uniquely? The authors discuss this and related problems briefly, referring to a later publication. They observe, for example, that if \(\mathcal K\) is the class of paths and \(G\) is a tree, then \(G\) need not be reconstructible this way, but that the question is open when, say, \(\mathcal K\) is the class of caterpillars or disjoint unions of paths.
They then pose another strengthening of the reconstruction conjecture, namely, the study of the function \(L(n)\) defined as follows. Let \(L(n)\) denote the smallest positive integer \(m\) such that all graphs of order \(n\) are determined by their induced subgraphs of order \(m\). The authors give the first eight values of \(L(n)\) and observe that, assuming that the reconstruction conjecture is true, the plot of \(L(n)\) against \(n\) lies below the straight line \(y=x-1\); but by a result of V. Nýdl [Discrete Math. 108, 373–377 (1992; Zbl 0759.05067)], it does not lie below any straight line passing through the origin and with slope \(q<1\). (The authors call the function \(L\) the Ulam-ladder.)


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


Zbl 0759.05067
Full Text: EuDML


[1] Bollobás B.: Almost every graph has reconstruction number three. J. Graph Theory 14 (1990), 1-4 · Zbl 0702.05061
[2] Bondy J. A.: A Graph Reconstructor’s Manual. : Lecture Notes LMS, vol. 166, Cambridge Univ. Press. 1991. · Zbl 0741.05052
[3] Dulio P., Pannone V.: Trees with the same path-table. submitted. · Zbl 1118.05014
[4] Geller D., Manvel B.: Reconstruction of cacti. Canad. J. Math. 21 (1969), 1354-1360. · Zbl 0187.21401
[5] Greenwell D. L., Hemminger R. L.: Reconstructing the \(n\)-connected components of a graph. Aequationes Math. 9 (1973), 19-22. · Zbl 0255.05125
[6] Harary F., Plantholt M.: The Graph Reconstruction Number. J. Graph Theory 9 (1985), 451-454. · Zbl 0664.05043
[7] Kelly P. J.: A congruence Theorem for Trees. Pacific J. Math. 7 (1957), 961-968. · Zbl 0078.37103
[8] Lauri J.: The reconstruction of maximal planar graphs. II. Reconstruction. J. Combin. Theory, Ser. B 30, 2 (1981), 196-214. · Zbl 0413.05036
[9] Lauri J.: Graph reconstruction-some techniques and new problems. Ars Combinatoria, ser. B 24 (1987), 35-61. · Zbl 0659.05068
[10] Monson S. D.: The reconstruction of cacti revisited. Congr. Numer. 69 (1989), 157-166. · Zbl 0678.05040
[11] Nýdl V.: Finite undirected graphs which are not reconstructible from their large cardinality subgraphs. Discrete Math. 108 (1992), 373-377. · Zbl 0759.05067
[12] Tutte W. T.: All the king’s horses. A guide to reconstruction. Graph Theory and Related Topics, Acad. Press, New York, 1979 · Zbl 0472.05046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.