Geodesic
Reconstruction conjecture for graphs with restrictions for 4-vertex paths
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 4, pp. 87-96.

Voir la notice de l'article provenant de la source Math-Net.Ru

The well-known Kelly–Ulam reconstruction conjecture is considered. It is proved that the conjecture holds for $P_4$-disconnected and $P_4$-tidy graphs. In particular, it generalizes the known results on the reconstructibility of disconnected graphs, complements of disconnected graphs, 1-decomposable graphs, and $P_4$-reducible graphs. Bibl. 19.
Mots-clés : reconstruction conjecture
Keywords: $P_4$-disconnected graphs, $P_4$-tidy graphs, $P_4$-reducible graphs, 1-decomposable graphs. 
@article{DA_2009_16_4_a5,
     author = {P. V. Skums and R. I. Tyshkevich},
     title = {Reconstruction conjecture for graphs with restrictions for 4-vertex paths},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {87--96},
     publisher = {mathdoc},
     volume = {16},
     number = {4},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_4_a5/}
}
TY  - JOUR
AU  - P. V. Skums
AU  - R. I. Tyshkevich
TI  - Reconstruction conjecture for graphs with restrictions for 4-vertex paths
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 87
EP  - 96
VL  - 16
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_4_a5/
LA  - ru
ID  - DA_2009_16_4_a5
ER  - 
%0 Journal Article
%A P. V. Skums
%A R. I. Tyshkevich
%T Reconstruction conjecture for graphs with restrictions for 4-vertex paths
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 87-96
%V 16
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2009_16_4_a5/
%G ru
%F DA_2009_16_4_a5
P. V. Skums; R. I. Tyshkevich. Reconstruction conjecture for graphs with restrictions for 4-vertex paths. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 4, pp. 87-96. http://geodesic.mathdoc.fr/item/DA_2009_16_4_a5/

[1] Tyurin V., “Rekonstruktsiya razlozhimykh grafov”, Vesti AN BSSR, 1987, no. 3, 16–20 | MR | Zbl

[2] Babel L., “Tree-like $P_4$-connected graphs”, Discrete Math, 191 (1998), 13–23 | DOI | MR | Zbl

[3] Babel L., Olariu S., “On the isomorphism of graphs with few $P_4$s”, Discrete Appl. Math., 84 (1998), 1–3 | DOI | MR | Zbl

[4] Babel L., Olariu S., “On the $p$-connectedness of graphs – a survey”, Discrete Appl. Math., 95 (1999), 11–33 | DOI | MR | Zbl

[5] Biggs N., Algebraic graph theory, Cambridge Univ. Press, Cambridge, 1996, 316 pp. | MR | Zbl

[6] Bondy A., “A graph reconstructor's manual”, Surveys in Combinatorics, London Math. Soc. Lecture Notes Series, Cambridge Univ. Press, Cambridge, 1991, 221–252 | MR

[7] Bondy A., Hemminger R. L., “Graph reconstruction – a survey”, J. Graph Theory, 1 (1977), 227–268 | DOI | MR | Zbl

[8] Brandstädt A., Le V. B., Spinrad J., Graph classes: a survey, SIAM, Philadelphia, 1999, 95 pp. | MR | Zbl

[9] Giakoumakis V., Roussel F., Thuillier H., “On $P_4$-tidy graphs”, Discrete Math. and Theor. Comp. Sci., 1:1 (1997), 17–41 | MR | Zbl

[10] Hammer P. L., Simeone B., “The splittence of a graph”, Combinatorica, 3:1 (1981), 275–284 | DOI | MR

[11] Hell P., Nesetril J., Graphs and homomorphisms, Oxford Univ. Press, Oxford, 2004, 256 pp. | MR | Zbl

[12] Jamison B., Olariu S., “$p$-Components and the homogeneous decomposition of graphs”, SIAM J. Discrete Math., 8 (1995), 448–463 | DOI | MR | Zbl

[13] Kelly P. J., On isometric transformations, PhD thesis, University of Wisconsin, 1942, 95 pp.

[14] Lauri J., Scapellato R., Topics in graph isomorphisms and reconstruction, Cambridge Univ. Press, Cambridge, 2003, 172 pp. | MR | Zbl

[15] Mahadev N. V., Peled U. N., Threshold graphs and related topics, Annals of Discrete Math., 56, 1995, 558 pp. | MR | Zbl

[16] Thatte B., “Some results on the reconstruction problem. $p$-Claw-free, chordal and $P_4$-reducible graphs”, J. Graph Theory, 19:4 (1995), 549–561 | DOI | MR | Zbl

[17] Tyshkevich R., “Decomposition of graphical sequences and unigraphs”, Discrete Math., 220 (2000), 201–238 | DOI | MR | Zbl

[18] Tyshkevich R., Chernyak A., “Decomposition of graphs”, Cybernetics, 21 (1985), 231–242 | DOI | MR

[19] Ulam S. M., A collection of mathematical problems, Wiley (Interscience), New York, 1960, 150 pp. | MR