MATHEMATICA BOHEMICA, Vol. 127, No. 4, pp. 557-570 (2002)

# On \$k\$-strong distance in strong digraphs

## Ping Zhang

Ping Zhang, Department of Mathematics and Statistics, Western Michigan University, Kalamazoo, MI 49008, USA, e-mail: ping.zhang@wmich.edu

Abstract: 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.

Keywords: strong distance, strong eccentricity, strong center, strong periphery

Classification (MSC2000): 05C12, 05C20

Full text of the article:

[Previous Article] [Next Article] [Contents of this Number]
© 2005 ELibM and FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition