| Title:
|
The converse of Kelly’s lemma and control-classes in graph reconstruction (English) |
| Author:
|
Dulio, Paolo |
| Author:
|
Pannone, Virgilio |
| Language:
|
English |
| Journal:
|
Acta Universitatis Palackianae Olomucensis. Facultas Rerum Naturalium. Mathematica |
| ISSN:
|
0231-9721 |
| Volume:
|
44 |
| Issue:
|
1 |
| Year:
|
2005 |
| Pages:
|
25-38 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
Graph |
| Keyword:
|
Kelly’s Lemma |
| Keyword:
|
Reconstruction |
| MSC:
|
05C05 |
| MSC:
|
05C60 |
| idZBL:
|
Zbl 1086.05051 |
| idMR:
|
MR2218565 |
| . |
| Date available:
|
2009-08-21T06:49:05Z |
| Last updated:
|
2012-05-04 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/133380 |
| . |
| Reference:
|
[1] Bollobás B.: Almost every graph has reconstruction number three.J. Graph Theory 14 (1990), 1–4 Zbl 0702.05061, MR 1037416 |
| Reference:
|
[2] Bondy J. A.: A Graph Reconstructor’s Manual. : Lecture Notes LMS, vol. 166, Cambridge Univ. Press., 1991. MR 1161466 |
| Reference:
|
[3] Dulio P., Pannone V.: Trees with the same path-table.submitted. Zbl 1118.05014 |
| Reference:
|
[4] Geller D., Manvel B.: Reconstruction of cacti.Canad. J. Math. 21 (1969), 1354–1360. Zbl 0187.21401, MR 0252255 |
| Reference:
|
[5] Greenwell D. L., Hemminger R. L.: Reconstructing the $n$-connected components of a graph.Aequationes Math. 9 (1973), 19–22. Zbl 0255.05125, MR 0384614 |
| Reference:
|
[6] Harary F., Plantholt M.: The Graph Reconstruction Number.J. Graph Theory 9 (1985), 451–454. Zbl 0664.05043, MR 0890233 |
| Reference:
|
[7] Kelly P. J.: A congruence Theorem for Trees.Pacific J. Math. 7 (1957), 961–968. Zbl 0078.37103, MR 0087949 |
| Reference:
|
[8] Lauri J.: The reconstruction of maximal planar graphs. II. Reconstruction.J. Combin. Theory, Ser. B 30, 2 (1981), 196–214. Zbl 0413.05036, MR 0615314 |
| Reference:
|
[9] Lauri J.: Graph reconstruction-some techniques and new problems.Ars Combinatoria, ser. B 24 (1987), 35–61. Zbl 0659.05068, MR 0941788 |
| Reference:
|
[10] Monson S. D.: The reconstruction of cacti revisited.Congr. Numer. 69 (1989), 157–166. Zbl 0678.05040, MR 0995883 |
| Reference:
|
[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, MR 1189858 |
| Reference:
|
[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). Zbl 0472.05046, MR 0538033 |
| . |
