Geodesic
Reconstruction of Cacti
Canadian journal of mathematics, Tome 21 (1969) no. 1, pp. 1354-1360

Voir la notice de l'article provenant de la source Cambridge University Press

Following the work of Kelly (8), Harary and Palmer (5), and Bondy (1) on the reconstruction of trees, and of Manvel (10) on the reconstruction of connected graphs with a single cycle, it was a natural step to attempt to solve the reconstruction problem for cacti. The solution of this problem, presented here, assumes both Kelly's Theorem and the result of Manvel in (10). Any definitions not given here can be found in (2).Let graph G have point set V = {v1 v2, ..., vp} and line set X = {x1, x2, ..., xq}. For each vi ∈ V, Gi = G – vi is the maximal subgraph of G which does not contain vi and is formed by deleting vi and all lines incident with it from G. 
Geller, Dennis; Manvel, Bennet. Reconstruction of Cacti. Canadian journal of mathematics, Tome 21 (1969) no. 1, pp. 1354-1360. doi: 10.4153/CJM-1969-149-3
@article{10_4153_CJM_1969_149_3,
     author = {Geller, Dennis and Manvel, Bennet},
     title = {Reconstruction of {Cacti}},
     journal = {Canadian journal of mathematics},
     pages = {1354--1360},
     year = {1969},
     volume = {21},
     number = {1},
     doi = {10.4153/CJM-1969-149-3},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1969-149-3/}
}
TY  - JOUR
AU  - Geller, Dennis
AU  - Manvel, Bennet
TI  - Reconstruction of Cacti
JO  - Canadian journal of mathematics
PY  - 1969
SP  - 1354
EP  - 1360
VL  - 21
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1969-149-3/
DO  - 10.4153/CJM-1969-149-3
ID  - 10_4153_CJM_1969_149_3
ER  - 
%0 Journal Article
%A Geller, Dennis
%A Manvel, Bennet
%T Reconstruction of Cacti
%J Canadian journal of mathematics
%D 1969
%P 1354-1360
%V 21
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1969-149-3/
%R 10.4153/CJM-1969-149-3
%F 10_4153_CJM_1969_149_3

[1] 1. Bondy, J. A., Ow Kelly's congruence theorem for trees, Proc. Cambridge Philos. Soc. 65 (1969), 387–397. Google Scholar

[2] 2. Harary, F., Graph theory (Addison-Wesley, Reading, Massachusetts, 1969). Google Scholar

[3] 3. On the reconstruction of a graph from a collection of subgraphs, pp. 47-52 in Theory of graphs and its applications, edited by Fiedler, M. (Academic Press, New York, 1964). Google Scholar

[4] 4. Harary, F. and Anderson, S., Trees and unicyclic graphs, Math. Teacher 60 (1967), 345–348. Google Scholar

[5] 5. Harary, F. and Palmer, E. M., The reconstruction of a tree from its maximal subtrees, Can. J. Math. 18 (1966), 803–810. Google Scholar

[6] 6. Harary, F. and Uhlenbeck, G. E., On the number of Husimi trees, Proc. Nat. Acad. Sci. U.S.A. 39 (1953), 315–322. Google Scholar

[7] 7. Husimi, K., Note on Mayer's theory of cluster integrals, J. Chem. Phys. 18 (1950), 682–684. Google Scholar

[8] 8. Kelly, P. J., A congruence theorem for trees, Pacific J. Math. 7 (1957), 961–968. Google Scholar

[9] 9. Kônig, D., Théorie der endlichen und unendlichen Graphen (Leipzig, Berlin, 1936; reprinted by Chelsea, New York, 1950). Google Scholar

[10] 10. Manvel, B., Reconstruction of unicyclic graphs, pp. 103—107 in Proof techniques in graph theory, edited by Harary, F. (Academic Press, New York, 1969). Google Scholar

[10] 10. Ulam, S. M., A collection of mathematical problems, p. 29 (Interscience, New York, 1960). Google Scholar

Cité par Sources :