×

On peripheral vertices in graphs. (English) Zbl 0702.05049

Topics in combinatorics and graph theory. Essays in honour of Gerhard Ringel, 193-199 (1990).
Summary: [For the entire collection see Zbl 0698.00017.]
The periphery of a graph G is the subgraph of G induced by the vertices in G whose eccentricity equals the diameter of G. Graphs that are peripheries of graphs with specified diameter are characterized. For a graph G, the antipodal graph A(G) of G is the graph having the same vertex set as G and edge set \(E(A(G))=\{uv| u\), \(v\in V(G)\) and \(d_ G(u,v)=diam G\}\). For a graph G and positive integer n, the nth iterated antipodal graph \(A^ n(G)\) of G is defined as the graph \(A(A^{n- 1}(G))\) where \(A^ 1(G)\) is A(G) and \(A^ 0(G)\) denotes G. It is shown that there exist nonnegative integers \(n_ 1\) and \(n_ 2\) such that \(n_ 1<n_ 2\) and \(A^{n_ 1}(G)\cong A^{n_ 2}(G)\). The smallest positive integer k for which there exists an integer \(\ell\) such that \(A^{\ell}(G)\cong A^{\ell +k}(G)\) is called the antipodal period of G. It is shown that for every positive integer k there exists a graph with antipodal period k.

MSC:

05C38 Paths and cycles
05C35 Extremal problems in graph theory

Citations:

Zbl 0698.00017