Premium
Eccentric graphs
Author(s) -
Chartrand Gary,
Gu Weizhen,
Schultz Michelle,
Winters Steven J.
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199909)34:2<115::aid-net4>3.0.co;2-k
Subject(s) - vertex (graph theory) , combinatorics , mathematics , neighbourhood (mathematics) , graph , discrete mathematics , mathematical analysis
The eccentricity e ( v ) of a vertex v in a connected graph G is the distance between v and a vertex farthest from v . A vertex u is an eccentric vertex of v if d ( u, v ) = e ( v ). A vertex w of G is an eccentric vertex of G if w is an eccentric vertex of some vertex of G . The eccentricity e ( G ) of G is the minimum integer k such that every vertex of G with eccentricity at least k is an eccentric vertex. A graph G is an eccentric graph if every vertex of G is an eccentric vertex or, equivalently, if the radius of G equals e ( G ). It is shown that for every pair a, c of positive integers satisfying a ≤ c ≤ 2 a there exists an eccentric graph G with rad G = a and diam G = c . Moreover, for every connected graph G , there exists a connected graph H containing G as an induced subgraph such that V ( G ) is the set of eccentric vertices of H if and only if every vertex of G has eccentricity 1 or no vertex of G has eccentricity 1. Similar characterizations are presented for graphs that are the center or periphery of some eccentric graph. © 1999 John Wiley & Sons, Inc. Networks 34: 115–121, 1999