Two classes of graphs related to extremal eccentricities

Abstract: A graph $G$ is called an $S$-graph if its periphery $\mathop Peri(G)$ is equal to its center eccentric vertices $\mathop Cep(G)$. Further, a graph $G$ is called a $D$-graph if $\mathop Peri(G)\cap\mathop Cep(G)=\emptyset$.

We describe $S$-graphs and $D$-graphs for small radius. Then, for a given graph $H$ and natural numbers $r\ge2$, $n\ge2$, we construct an $S$-graph of radius $r$ having $n$ central vertices and containing $H$ as an induced subgraph. We prove an analogous existence theorem for $D$-graphs, too. At the end, we give some properties of $S$-graphs and $D$-graphs.

Keywords: eccentricity, central vertex, peripheral vertex

Classification (MSC2000): 05C12, 05C35

Full text of the article:

• Compressed PostScript file (261 kilobytes)
• PDF file (575 kilobytes)