Eccentric completion of a graph

Document Type : Original paper


CHRIST (Deemed to be University), Bangalore


The eccentric graph $G_e$ of a graph $G$ is a derived graph with the vertex set same as that of $G$ and two vertices in $G_e$ are adjacent if one of them is the eccentric vertex of the other. In this paper, the concepts of iterated eccentric graphs and eccentric completion of a graph are introduced and discussed.


Main Subjects

[1] J. Akiyama, K. Ando, and D. Avis, Eccentric graphs, Discrete Math. 56 (1985), no. 1, 1–6.
[2] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, 1990.
[3] G. Chartrand, W. Gu, M. Schultz, and S.J. Winters, Eccentric graphs, Networks 34 (1999), no. 2, 115–121.
[4] P. Dankelmann, New bounds on proximity and remoteness in graphs, Commun. Comb. Optim. 1 (2016), no. 1, 29–41.
[5] J. Gimbert, M. Miller, F. Ruskey, and J. Ryan, Iterations of eccentric digraphs, Bull. Inst. Combin. Appl. 45 (2005), 41–50.
[6] J. T. Hedetniemi, S. T. Hedetniemi, R. C. Laskar, C. Renu, and H. M. Mulder, Different-distance sets in a graph, Commun. Comb. Optim. 4 (2019), no. 2, 151–171.
[7] J. V. Kureethara and M. Sebastian, Line completion number of grid graph  ppm , Commun. Comb. Optim. 6 (2021), no. 2, 299–313.
[8] E. Prisner, Graph Dynamics, vol. 338, CRC Press, 1995.
[9] D. B. West, Introduction to Graph Theory, vol. 2, Prentice hall of India, New Delhi, 2001.