Geodesic
The converse of Kelly’s lemma and control-classes in graph reconstruction
Acta Universitatis Palackianae Olomucensis. Facultas Rerum Naturalium. Mathematica, Tome 44 (2005) no. 1, pp. 25-38 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C05, 05C60
Keywords: Graph; Kelly’s Lemma; Reconstruction 
@article{AUPO_2005_44_1_a3,
     author = {Dulio, Paolo and Pannone, Virgilio},
     title = {The converse of {Kelly{\textquoteright}s} lemma and control-classes in graph reconstruction},
     journal = {Acta Universitatis Palackianae Olomucensis. Facultas Rerum Naturalium. Mathematica},
     pages = {25--38},
     year = {2005},
     volume = {44},
     number = {1},
     mrnumber = {2218565},
     zbl = {1086.05051},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/AUPO_2005_44_1_a3/}
}
TY  - JOUR
AU  - Dulio, Paolo
AU  - Pannone, Virgilio
TI  - The converse of Kelly’s lemma and control-classes in graph reconstruction
JO  - Acta Universitatis Palackianae Olomucensis. Facultas Rerum Naturalium. Mathematica
PY  - 2005
SP  - 25
EP  - 38
VL  - 44
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/AUPO_2005_44_1_a3/
LA  - en
ID  - AUPO_2005_44_1_a3
ER  - 
%0 Journal Article
%A Dulio, Paolo
%A Pannone, Virgilio
%T The converse of Kelly’s lemma and control-classes in graph reconstruction
%J Acta Universitatis Palackianae Olomucensis. Facultas Rerum Naturalium. Mathematica
%D 2005
%P 25-38
%V 44
%N 1
%U http://geodesic.mathdoc.fr/item/AUPO_2005_44_1_a3/
%G en
%F AUPO_2005_44_1_a3
Dulio, Paolo; Pannone, Virgilio. The converse of Kelly’s lemma and control-classes in graph reconstruction. Acta Universitatis Palackianae Olomucensis. Facultas Rerum Naturalium. Mathematica, Tome 44 (2005) no. 1, pp. 25-38. http://geodesic.mathdoc.fr/item/AUPO_2005_44_1_a3/

[1] Bollobás B.: Almost every graph has reconstruction number three. J. Graph Theory 14 (1990), 1–4 | MR | Zbl

[2] Bondy J. A.: A Graph Reconstructor’s Manual. : Lecture Notes LMS, vol. 166, Cambridge Univ. Press. 1991. | MR

[3] Dulio P., Pannone V.: Trees with the same path-table. submitted. | Zbl

[4] Geller D., Manvel B.: Reconstruction of cacti. Canad. J. Math. 21 (1969), 1354–1360. | MR | Zbl

[5] Greenwell D. L., Hemminger R. L.: Reconstructing the $n$-connected components of a graph. Aequationes Math. 9 (1973), 19–22. | MR | Zbl

[6] Harary F., Plantholt M.: The Graph Reconstruction Number. J. Graph Theory 9 (1985), 451–454. | MR | Zbl

[7] Kelly P. J.: A congruence Theorem for Trees. Pacific J. Math. 7 (1957), 961–968. | MR | Zbl

[8] Lauri J.: The reconstruction of maximal planar graphs. II. Reconstruction. J. Combin. Theory, Ser. B 30, 2 (1981), 196–214. | MR | Zbl

[9] Lauri J.: Graph reconstruction-some techniques and new problems. Ars Combinatoria, ser. B 24 (1987), 35–61. | MR | Zbl

[10] Monson S. D.: The reconstruction of cacti revisited. Congr. Numer. 69 (1989), 157–166. | MR | Zbl

[11] Nýdl V.: Finite undirected graphs which are not reconstructible from their large cardinality subgraphs. Discrete Math. 108 (1992), 373–377. | MR | Zbl

[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 | Zbl