1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

On Subgraphs with Prescribed Eccentricities

Published Online: 18 Mar 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 05 Dec 2019
Accepted: 02 Feb 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

A well-known result by Hedetniemi states that for every graph G there is a graph H whose center is G. We extend this result by showing under which conditions there exists, for a given graph G in which each vertex v has an integer label (v), a graph H containing G as an induced subgraph such that the eccentricity, in H, of every vertex v of G equals (v). Such a labelled graph G is said to be eccentric, and strictly eccentric if there exists such a graph H such that no vertex of HG has the same eccentricity in H as any vertex of G. We find necessary and su cient conditions for a labelled graph to be eccentric and for a forest to be eccentric or strictly eccentric in a tree.

Keywords

MSC 2010

[1] F. Buckley, Z. Miller and P.J. Slater, On graphs containing a given graph as center, J. Graph Theory 5 (1981) 427–434. doi:10.1002/jgt.319005041310.1002/jgt.3190050413Search in Google Scholar

[2] G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman and Hall, New York, 1996).Search in Google Scholar

[3] G. Chartrand, M. Schultz and S.J. Winters, On eccentric vertices in graphs, Networks 28 (1996) 181–186. doi:10.1002/(SICI)1097-0037(199612)28:4〈181::AID-NET2〉3.0.CO;2-HSearch in Google Scholar

[4] P. Dankelmann, D.J. Erwin, W. Goddard, S. Mukwembi and H.C. Swart, Eccentric counts, connectivity and chordality, Inform. Process. Lett. 112 (2012) 944–947. doi:10.1016/j.ipl.2012.08.02210.1016/j.ipl.2012.08.022Search in Google Scholar

[5] P. Dankelmann, D.J. Erwin, W. Goddard, S. Mukwembi and H.C. Swart, A char-acterisation of eccentric sequences of maximal outerplanar graphs, Australas. J. Combin. 58 (2014) 376–391.Search in Google Scholar

[6] P. Dankelmann, D. Erwin, and H. Swart, On digraphs with prescribed eccentricities, J. Combin. Math. Combin. Comput. 104 (2018) 143–160.Search in Google Scholar

[7] D.J. Erwin and F. Harary, Destroying automorphisms by fixing nodes, Discrete Math. 306 (2006) 3244–3252. doi:10.1016/j.disc.2006.06.00410.1016/j.disc.2006.06.004Search in Google Scholar

[8] D. Ferrero and F. Harary, On eccentricity sequences of connected graphs, AKCE Int. J. Graphs Comb. 6 (2009) 401–408.Search in Google Scholar

[9] J. Gimbert and N. López, Eccentricity sequences and eccentricity sets in digraphs, Ars Combin. 86 (2008) 225–238.Search in Google Scholar

[10] S. Gupta, M. Singh and A.K. Madan, Eccentric distance sum: A novel graph invariant for predicting biological and physical properties, J. Math. Anal. Appl. 275 (2002) 386–401. doi:10.1016/S0022-247X(02)00373-610.1016/S0022-247X(02)00373-6Search in Google Scholar

[11] A. Haviar, P. Hrnčiar and G. Monoszová, Minimal eccentric sequences with least eccentricity three, Acta Univ. M. Belii Ser. Math. 5 (1997) 27–50.Search in Google Scholar

[12] M. Harminc and J. Ivančo, Note on eccentricities in tournaments, Graphs Combin. 10 (1994) 231–234. doi:10.1007/BF0298667010.1007/BF02986670Search in Google Scholar

[13] L. Lesniak, Eccentric sequences in graphs, Period. Math. Hungar. 6 (1975) 287–293. doi:10.1007/BF0201792510.1007/BF02017925Search in Google Scholar

[14] V. Mukungunugwa and S. Mukwembi, On eccentric distance sum and minimum degree, Discrete Appl. Math. 175 (2014) 55–61. doi:10.1016/j.dam.2014.05.01910.1016/j.dam.2014.05.019Search in Google Scholar

[15] D. Mubayi and D.B. West, On the number of vertices with specified eccentricity, Graphs Combin. 16 (2000) 441–452. doi:10.1007/PL0000722910.1007/PL00007229Search in Google Scholar

[16] R. Nandakumar, On Some Eccentric Properties of Graphs, Ph.D. Thesis (Indian Institute of Technology, New Delhi, 1986).Search in Google Scholar

[17] O.R. Oellermann and S. Tian, Steiner n-eccentricity sequences of graphs, Recent Studies in Graph Theory (1989) 206–211.Search in Google Scholar

[18] A. Tamir, The k-centrum multi-facility location problem, Discrete Appl. Math. 109 (2001) 293–307. doi:10.1016/S0166-218X(00)00253-510.1016/S0166-218X(00)00253-5Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo