zbMATH — the first resource for mathematics

On \(k\)-strong distance in strong digraphs. (English) Zbl 1003.05037
Summary: For a nonempty set \(S\) of vertices in a strong digraph \(D\), the strong distance \(d(S)\) is the minimum size of a strong subdigraph of \(D\) containing the vertices of \(S\). If \(S\) contains \(k\) vertices, then \(d(S)\) is referred to as the \(k\)-strong distance of \(S\). For an integer \(k \geq 2\) and a vertex \(v\) of a strong digraph \(D\), the \(k\)-strong eccentricity se\(_k (v)\) of \(v\) is the maximum \(k\)-strong distance \(d(S)\) among all sets \(S\) of \(k\) vertices in \(D\) containing \(v\). The minimum \(k\)-strong eccentricity among the vertices of \(D\) is its \(k\)-strong radius srad\(_k D\) and the maximum \(k\)-strong eccentricity is its \(k\)-strong diameter sdiam\(_k D\). The \(k\)-strong center (\(k\)-strong periphery) of \(D\) is the subdigraph of \(D\) induced by those vertices of \(k\)-strong eccentricity srad\(_k(D)\) (sdiam\(_k (D)\)). It is shown that, for each integer \(k \geq 2\), every oriented graph is the \(k\)-strong center of some strong oriented graph. A strong oriented graph \(D\) is called strongly \(k\)-self-centered if \(D\) is its own \(k\)-strong center. For every integer \(r \geq 6\), there exist infinitely many strongly 3-self-centered oriented graphs of 3-strong radius \(r\). The problem of determining those oriented graphs that are \(k\)-strong peripheries of strong oriented graphs is studied.
05C12 Distance in graphs
05C20 Directed graphs (digraphs), tournaments
Full Text: EuDML