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.
MSC:
 05C12 Distance in graphs 05C20 Directed graphs (digraphs), tournaments
Full Text: