Geodesic
On subgraphs with prescribed eccentricities
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 685-702 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 H-G has the same eccentricity in H as any vertex of G. We find necessary and sufficient conditions for a labelled graph to be eccentric and for a forest to be eccentric or strictly eccentric in a tree.
Keywords: distance, eccentricity, subgraph, tree 
@article{DMGT_2023_43_3_a6,
     author = {Dankelmann, Peter and DeVilbiss, Matthew and Erwin, David J. and Guest, Kelly and Matzke, Ryan},
     title = {On subgraphs with prescribed eccentricities},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {685--702},
     year = {2023},
     volume = {43},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a6/}
}
TY  - JOUR
AU  - Dankelmann, Peter
AU  - DeVilbiss, Matthew
AU  - Erwin, David J.
AU  - Guest, Kelly
AU  - Matzke, Ryan
TI  - On subgraphs with prescribed eccentricities
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 685
EP  - 702
VL  - 43
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a6/
LA  - en
ID  - DMGT_2023_43_3_a6
ER  - 
%0 Journal Article
%A Dankelmann, Peter
%A DeVilbiss, Matthew
%A Erwin, David J.
%A Guest, Kelly
%A Matzke, Ryan
%T On subgraphs with prescribed eccentricities
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 685-702
%V 43
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a6/
%G en
%F DMGT_2023_43_3_a6
Dankelmann, Peter; DeVilbiss, Matthew; Erwin, David J.; Guest, Kelly; Matzke, Ryan. On subgraphs with prescribed eccentricities. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 685-702. http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a6/

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

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

[3] G. Chartrand, M. Schultz and S.J. Winters, On eccentric vertices in graphs, Networks 28 (1996) 181–186. https://doi.org/10.1002/(SICI)1097-0037(199612)28:43.0.CO;2-H

[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. https://doi.org/10.1016/j.ipl.2012.08.022

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

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

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

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

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

[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. https://doi.org/10.1016/S0022-247X(02)00373-6

[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.

[12] M. Harminc and J. Ivančo, Note on eccentricities in tournaments, Graphs Combin. 10 (1994) 231–234. https://doi.org/10.1007/BF02986670

[13] L. Lesniak, Eccentric sequences in graphs, Period. Math. Hungar. 6 (1975) 287–293. https://doi.org/10.1007/BF02017925

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

[15] D. Mubayi and D.B. West, On the number of vertices with specified eccentricity, Graphs Combin. 16 (2000) 441–452. https://doi.org/10.1007/PL00007229

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

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

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