The converse of Kelly’s lemma and control-classes in graph reconstruction
Acta Universitatis Palackianae Olomucensis. Facultas Rerum Naturalium. Mathematica (2005)
- Volume: 44, Issue: 1, page 25-38
- ISSN: 0231-9721
Access Full Article
top
Abstract
topHow to cite
topDulio, Paolo, and Pannone, Virgilio. "The converse of Kelly’s lemma and control-classes in graph reconstruction." Acta Universitatis Palackianae Olomucensis. Facultas Rerum Naturalium. Mathematica 44.1 (2005): 25-38. <http://eudml.org/doc/32448>.
@article{Dulio2005,
abstract = {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.},
author = {Dulio, Paolo, Pannone, Virgilio},
journal = {Acta Universitatis Palackianae Olomucensis. Facultas Rerum Naturalium. Mathematica},
keywords = {Graph; Kelly’s Lemma; Reconstruction},
language = {eng},
number = {1},
pages = {25-38},
publisher = {Palacký University Olomouc},
title = {The converse of Kelly’s lemma and control-classes in graph reconstruction},
url = {http://eudml.org/doc/32448},
volume = {44},
year = {2005},
}
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
PB - Palacký University Olomouc
VL - 44
IS - 1
SP - 25
EP - 38
AB - 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.
LA - eng
KW - Graph; Kelly’s Lemma; Reconstruction
UR - http://eudml.org/doc/32448
ER -
References
top- Bollobás B., Almost every graph has reconstruction number three, J. Graph Theory 14 (1990), 1–4 (1990) Zbl0702.05061MR1037416
- Bondy J. A.: A Graph Reconstructor’s Manual., Lecture Notes LMS, vol. 166, Cambridge Univ. Press, , 1991. (1991) MR1161466
- Dulio P., Pannone V., Trees with the same path-table, submitted. Zbl1118.05014
- Geller D., Manvel B., Reconstruction of cacti, Canad. J. Math. 21 (1969), 1354–1360. (1969) Zbl0187.21401MR0252255
- Greenwell D. L., Hemminger R. L., Reconstructing the -connected components of a graph, Aequationes Math. 9 (1973), 19–22. (1973) Zbl0255.05125MR0384614
- Harary F., Plantholt M., The Graph Reconstruction Number, J. Graph Theory 9 (1985), 451–454. (1985) Zbl0664.05043MR0890233
- Kelly P. J., A congruence Theorem for Trees, Pacific J. Math. 7 (1957), 961–968. (1957) Zbl0078.37103MR0087949
- Lauri J., The reconstruction of maximal planar graphs. II. Reconstruction, J. Combin. Theory, Ser. B 30, 2 (1981), 196–214. (1981) Zbl0413.05036MR0615314
- Lauri J., Graph reconstruction-some techniques and new problems, Ars Combinatoria, ser. B 24 (1987), 35–61. (1987) Zbl0659.05068MR0941788
- Monson S. D., The reconstruction of cacti revisited, Congr. Numer. 69 (1989), 157–166. (1989) Zbl0678.05040MR0995883
- Nýdl V., Finite undirected graphs which are not reconstructible from their large cardinality subgraphs, Discrete Math. 108 (1992), 373–377. (1992) Zbl0759.05067MR1189858
- 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). (1979) Zbl0472.05046MR0538033
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.