Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
Graph; Kelly’s Lemma; Reconstruction
Graph; Kelly’s Lemma; Reconstruction
Summary:
We prove a converse of the well-known Kelly’s Lemma. This motivates the introduction of the general notions of $\mathcal{K}$-table, $\mathcal{K}$-congruence and control-class.
References:
[1] Bollobás B.: Almost every graph has reconstruction number three. J. Graph Theory 14 (1990), 1–4 MR 1037416 | Zbl 0702.05061
[2] Bondy J. A.: A Graph Reconstructor’s Manual. : Lecture Notes LMS, vol. 166, Cambridge Univ. Press. 1991. MR 1161466
[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. MR 0252255 | Zbl 0187.21401
[5] Greenwell D. L., Hemminger R. L.: Reconstructing the $n$-connected components of a graph. Aequationes Math. 9 (1973), 19–22. MR 0384614 | Zbl 0255.05125
[6] Harary F., Plantholt M.: The Graph Reconstruction Number. J. Graph Theory 9 (1985), 451–454. MR 0890233 | Zbl 0664.05043
[7] Kelly P. J.: A congruence Theorem for Trees. Pacific J. Math. 7 (1957), 961–968. MR 0087949 | Zbl 0078.37103
[8] Lauri J.: The reconstruction of maximal planar graphs. II. Reconstruction. J. Combin. Theory, Ser. B 30, 2 (1981), 196–214. MR 0615314 | Zbl 0413.05036
[9] Lauri J.: Graph reconstruction-some techniques and new problems. Ars Combinatoria, ser. B 24 (1987), 35–61. MR 0941788 | Zbl 0659.05068
[10] Monson S. D.: The reconstruction of cacti revisited. Congr. Numer. 69 (1989), 157–166. MR 0995883 | 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. MR 1189858 | Zbl 0759.05067
[12] Tutte W. T.: All the king’s horses. A guide to reconstruction. In: Graph Theory and Related Topics, Acad. Press, New York, 1979 (pp. 15–33). MR 0538033 | Zbl 0472.05046
Search
Partner of
