Geodesic
A reduction of the Graph Reconstruction Conjecture
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 529-537.

Voir la notice de l'article provenant de la source Library of Science

A graph is said to be reconstructible if it is determined up to isomorphism from the collection of all its one-vertex deleted unlabeled subgraphs. Reconstruction Conjecture (RC) asserts that all graphs on at least three vertices are reconstructible. In this paper, we prove that interval-regular graphs and some new classes of graphs are reconstructible and show that RC is true if and only if all non-geodetic and non-interval-regular blocks G with diam(G) = 2 or diam(G) = diam(Ḡ) = 3 are reconstructible.
Keywords: reconstruction, diameter, geodetic graph, interval-regular graph 
@article{DMGT_2014_34_3_a4,
     author = {Monikandan, S. and Balakumar, J.},
     title = {A reduction of the {Graph} {Reconstruction} {Conjecture}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {529--537},
     publisher = {mathdoc},
     volume = {34},
     number = {3},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a4/}
}
TY  - JOUR
AU  - Monikandan, S.
AU  - Balakumar, J.
TI  - A reduction of the Graph Reconstruction Conjecture
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 529
EP  - 537
VL  - 34
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a4/
LA  - en
ID  - DMGT_2014_34_3_a4
ER  - 
%0 Journal Article
%A Monikandan, S.
%A Balakumar, J.
%T A reduction of the Graph Reconstruction Conjecture
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 529-537
%V 34
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a4/
%G en
%F DMGT_2014_34_3_a4
Monikandan, S.; Balakumar, J. A reduction of the Graph Reconstruction Conjecture. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 529-537. http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a4/

[1] J.A. Bondy and R.L. Hemminger, Graph reconstruction-a survey, J. Graph Theory 1 (1977) 227-268. doi:10.1002/jgt.3190010306

[2] J.A. Bondy, A graph reconstructor’s manual, in: Surveys in Combinatorics (Proc. 13th British Combin. Conf.), Guildford (Ed(s)), (London Math. Soc. Lecture Note Ser. 166, Cambridge University Press, Cambridge, 1991) 221-252.

[3] A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-regular Graphs (Springer-Verlag, Berlin, 1989). doi:10.1007/978-3-642-74341-2

[4] P.J. Cameron, Stories from the age of reconstruction, Congr. Numer. 113 (1996) 31-41.

[5] S. Fiorini and J. Lauri, The reconstruction of maximal planar graphs I: Recognition, J. Combin. Theory (B) 30 (1981) 188-195. doi:10.1016/0095-8956(81)90063-0

[6] H. Fleischner, The reconstruction of line critical blocks, Ars Combin. 7 (1979) 223-254.

[7] W.B. Giles, The reconstruction of outerplanar graphs, J. Combin. Theory (B) 16 (1974) 215-226. doi:10.1016/0095-8956(74)90066-5

[8] S.K. Gupta, P. Mangal and V. Paliwal, Some work towards the proof of the reconstruction conjecture, Discrete Math. 272 (2003) 291-296. doi:10.1016/S0012-365X(03)00198-5

[9] F. Harary, On the reconstruction of a graph from a collection of subgraphs, in: Theory of Graphs and its Applications, M. Fiedler (Ed(s)), (Academic Press, New York, 1964) 47-52.

[10] F. Harary, Graph Theory (Addison-Wesley, 1969).

[11] V. Krishnamoorthy and K.R. Parthasarathy, Reconstruction of critical blocks, J. Math. Phys. Scis. 13 (1979) 219-239.

[12] J. Lauri, The reconstruction of maximal planar graphs II: Reconstruction, J. Combin. Theory (B) 30 (1981) 196-214. doi:10.1016/0095-8956(81)90064-2

[13] J. Lauri and R. Scapellato, Topics in Graph Automorphisms and Reconstruction (Cambridge University Press, 2003).

[14] B. Manvel, Reconstruction of graphs-progress and prospects, Congr. Numer. 63 (1988) 177-187.

[15] B. Manvel and J. Weinstein, Nearly acyclic graphs are reconstructible, J. Graph Theory 2 (1978) 25-39. doi:10.1002/jgt.3190020105

[16] H.M. Mulder, (0, λ)-graph and n-cubes, Discrete Math. 28 (1979) 179-188. doi:10.1016/0012-365X(79)90095-5

[17] H.M. Mulder, The Interval Function of a Graph (Math. Centre Tracts, 132, Mathematisch Centrum, Amsterdam, 1980).

[18] C.St.J.A. Nash Williams, The Reconstruction Problem, in: Selected Topics in Graph Theory, L.W. Beineke and R.J. Wilson (Ed(s)), (Academic Press, London, 1978) 205-236.

[19] P.V. O’Neil, Reconstruction of a class of blocks, AMS Notices 21 (1974) A-39.

[20] K.R. Parthasarathy and N. Srinivasan, Geodetic blocks of diameter three, Combinatorica 4 (2-3) (1984) 197-206. doi:10.1007/BF02579221

[21] D.B. West, Introduction to Graph Theory, Second Edition (Prentice-Hall, Inc. (Pearson Education, Inc.) Indian Edition, 2005).

[22] Y. Yongzhi, The Reconstruction Conjecture is true if all 2-connected graphs are reconstructible, J. Graph Theory 12 (1988) 237-243. doi:10.1002/jgt.319012021