# A Reduction of the Graph Reconstruction Conjecture

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 3, page 529-537
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topS. Monikandan, and J. Balakumar. "A Reduction of the Graph Reconstruction Conjecture." Discussiones Mathematicae Graph Theory 34.3 (2014): 529-537. <http://eudml.org/doc/268082>.

@article{S2014,

abstract = {A graph is said to be reconstructible if it is determined up to isomor- phism 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(Ḡ) = diam(G) = 3 are reconstructible},

author = {S. Monikandan, J. Balakumar},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {reconstruction; diameter; geodetic graph; interval-regular graph},

language = {eng},

number = {3},

pages = {529-537},

title = {A Reduction of the Graph Reconstruction Conjecture},

url = {http://eudml.org/doc/268082},

volume = {34},

year = {2014},

}

TY - JOUR

AU - S. Monikandan

AU - J. Balakumar

TI - A Reduction of the Graph Reconstruction Conjecture

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 3

SP - 529

EP - 537

AB - A graph is said to be reconstructible if it is determined up to isomor- phism 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(Ḡ) = diam(G) = 3 are reconstructible

LA - eng

KW - reconstruction; diameter; geodetic graph; interval-regular graph

UR - http://eudml.org/doc/268082

ER -

## References

top- [1] J.A. Bondy and R.L. Hemminger, Graph reconstruction-a survey, J. Graph Theory 1 (1977) 227-268. doi:10.1002/jgt.3190010306[Crossref] Zbl0375.05040
- [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. Zbl0741.05052
- [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[Crossref] Zbl0747.05073
- [4] P.J. Cameron, Stories from the age of reconstruction, Congr. Numer. 113 (1996) 31-41. Zbl0895.05044
- [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[Crossref] Zbl0413.05035
- [6] H. Fleischner, The reconstruction of line critical blocks, Ars Combin. 7 (1979) 223-254. Zbl0422.05054
- [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[Crossref]
- [8] S.K. Gupta, P. Mangal and V. Paliwal, Some work towards the proof of the recon- struction conjecture, Discrete Math. 272 (2003) 291-296. doi:10.1016/S0012-365X(03)00198-5[Crossref]
- [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. Zbl0424.05039
- [12] J. Lauri, The reconstruction of maximal planar graphs II: Reconstruction, J. Com- bin. Theory (B) 30 (1981) 196-214. doi:10.1016/0095-8956(81)90064-2 [Crossref]
- [13] J. Lauri and R. Scapellato, Topics in Graph Automorphisms and Reconstruction (Cambridge University Press, 2003). Zbl1038.05025
- [14] B. Manvel, Reconstruction of graphs-progress and prospects, Congr. Numer. 63 (1988) 177-187. Zbl0671.05053
- [15] B. Manvel and J. Weinstein, Nearly acyclic graphs are reconstructible, J. Graph Theory 2 (1978) 25-39. doi:10.1002/jgt.3190020105[Crossref] Zbl0379.05043
- [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, Math- ematisch Centrum, Amsterdam, 1980). Zbl0446.05039
- [18] C.St.J.A. NashWilliams, 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, Combina- torica 4 (2-3) (1984) 197-206. doi:10.1007/BF02579221[Crossref] Zbl0554.05043
- [21] D.B.West, Introduction to Graph Theory, Second Edition (Prentice-Hall, Inc. (Pear- son Education, Inc.) Indian Edition, 2005). Zbl1121.05304
- [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 [Crossref] Zbl0647.05041

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.