Previous |  Up |  Next


eccentricity; central vertex; peripheral vertex
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.
[1] Buckley F., Harary F.: Distance in Graphs. Addison-Wesley, New York, 1990. Zbl 0688.05017
[2] Buckley F., Lewinter M.: Graphs with diametral paths through distant central nodes. Math. Comput. Modelling 17 (1993), no. 11, 35-41. DOI 10.1016/0895-7177(93)90250-3 | MR 1236507
[3] Buckley F., Lewinter M.: Minimal graph embeddings, eccentric vertices and the peripherian. Proc. Fifth Caribbean Conference on Combinatorics and Computing. University of the West Indies, 1988, pp. 72-84.
[4] Gliviak F.: On radially critical graphs. Recent Advances in Graph Theory, Proc. Int. Symp. Prague 1974, Academia Press, Prague, 1975, pp. 207-221. MR 0384613
[5] Lewinter M.: Graphs with special distance properties. Quo Vadis Graph Theory? (J. Gimbel, J.W. Kennedy and L. V. Quintas, eds.). Annals of Discrete Mathematics Vol. 55, Elsevier, Amsterdam, 89-92. DOI 10.1016/S0167-5060(08)70378-9 | MR 1217982
Partner of
EuDML logo