# Article

Full entry | PDF   (1.9 MB)
Keywords:
graph; radius; diameter; center; eccentricity; distance
Summary:
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.
References:
[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