Article in volume
Authors:
Title:
On subgraphs with prescribed eccentricities
PDFSource:
Discussiones Mathematicae Graph Theory 43(3) (2023) 685-702
Received: 2019-12-05 , Revised: 2021-02-02 , Accepted: 2021-02-02 , Available online: 2021-02-19 , https://doi.org/10.7151/dmgt.2396
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 $\ell(v)$, a graph $H$ containing $G$ as an induced subgraph such
that the eccentricity, in $H,$ of every vertex $v$ of $G$ equals $\ell(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
References:
- 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 - G. Chartrand and L. Lesniak, Graphs and Digraphs (Chapman and Hall, New York, 1996).
- 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:4<181::AID-NET2>3.0.CO;2-H - 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 - 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.
- P. Dankelmann, D. Erwin, and H. Swart, On digraphs with prescribed eccentricities, J. Combin. Math. Combin. Comput. 104 (2018) 143–160.
- 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 - D. Ferrero and F. Harary, On eccentricity sequences of connected graphs, AKCE Int. J. Graphs Comb. 6 (2009) 401–408.
- J. Gimbert and N. López, Eccentricity sequences and eccentricity sets in digraphs, Ars Combin. 86 (2008) 225–238.
- 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 - 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.
- M. Harminc and J. Ivančo, Note on eccentricities in tournaments, Graphs Combin. 10 (1994) 231–234.
https://doi.org/10.1007/BF02986670 - L. Lesniak, Eccentric sequences in graphs, Period. Math. Hungar. 6 (1975) 287–293.
https://doi.org/10.1007/BF02017925 - 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 - 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 - R. Nandakumar, On Some Eccentric Properties of Graphs, Ph.D. Thesis (Indian Institute of Technology, New Delhi, 1986).
- O.R. Oellermann and S. Tian, Steiner $n$-eccentricity sequences of graphs, Recent Studies in Graph Theory (1989) 206–211.
- 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
Close