Previous |  Up |  Next


graph; radius; diameter; center; eccentricity; distance
The eccentricity $e(v)$ of a vertex $v$ is the distance from $v$ to a vertex farthest from $v$, and $u$ is an eccentric vertex for $v$ if its distance from $v$ is $d(u,v) = e(v)$. A vertex of maximum eccentricity in a graph $G$ is called peripheral, and the set of all such vertices is the peripherian, denoted $\mathop PeriG)$. We use $\mathop Cep(G)$ to denote the set of eccentric vertices of vertices in $C(G)$. A graph $G$ is called an S-graph if $\mathop Cep(G) = \mathop Peri(G)$. In this paper we characterize S-graphs with diameters less or equal to four, give some constructions of S-graphs and investigate S-graphs with one central vertex. We also correct and generalize some results of F. Gliviak.
[1] Chаrtrаnd G., Lesniаk L.: Graphs and Digraphs. Wadsworth and Brooks, Monterey, California, 1986.
[2] Buckley F., Lewïnter M.: Minimal graph embeddings, eccentric vertices and the peripherian. Proc. Fifth Carribean Conference on Cornbinatorics and Computing. University of the West Indies, 1988, pp. 72-84.
[3] Buckley P., Lewinter M.: Graphs with all diametral paths through distant central vertices. Math. Comput. Modelling 17 (1993), 35-41. DOI 10.1016/0895-7177(93)90250-3 | MR 1236507
[4] Gliviаk F.: Two classes of graphs related to extrernal eccentricities. Math. Bohem. 122 (1997), 231-241. MR 1600875
[5] Ore O.: Diameters in graphs. J.Combin.Theory 5 (1968), 75-81. DOI 10.1016/S0021-9800(68)80030-4 | MR 0227043 | Zbl 0175.20804
Partner of
EuDML logo