| Title:
|
On $k$-strong distance in strong digraphs (English) |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
127 |
| Issue:
|
4 |
| Year:
|
2002 |
| Pages:
|
557-570 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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 \ge 2$ and a vertex $v$ of a strong digraph $D$, the $k$-strong eccentricity $\mathop {\mathrm 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 $\mathop {\mathrm srad}_k D$ and the maximum $k$-strong eccentricity is its $k$-strong diameter $_k D$. The $k$-strong center ($k$-strong periphery) of $D$ is the subdigraph of $D$ induced by those vertices of $k$-strong eccentricity $\mathop {\mathrm srad}_k(D)$ ($_k (D)$). It is shown that, for each integer $k \ge 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 \ge 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. (English) |
| Keyword:
|
strong distance |
| Keyword:
|
strong eccentricity |
| Keyword:
|
strong center |
| Keyword:
|
strong periphery |
| MSC:
|
05C12 |
| MSC:
|
05C20 |
| idZBL:
|
Zbl 1003.05037 |
| idMR:
|
MR1942641 |
| DOI:
|
10.21136/MB.2002.133957 |
| . |
| Date available:
|
2009-09-24T22:05:07Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/133957 |
| . |
| Reference:
|
[1] F. Buckley, Z. Miller, P. J. Slater: On graphs containing a given graph as center.J. Graph Theory 5 (1981), 427–434. MR 0635706, 10.1002/jgt.3190050413 |
| Reference:
|
[2] G. Chartrand, D. Erwin, M. Raines, P. Zhang: Strong distance in strong digraphs.J. Combin. Math. Combin. Comput. 31 (1999), 33–44. MR 1726945 |
| Reference:
|
[3] G. Chartrand, D. Erwin, M. Raines, P. Zhang: On strong distance in strong oriented graphs.Congr. Numer. 141 (1999), 49–63. MR 1744211 |
| Reference:
|
[4] G. Chartrand, L. Lesniak: Graphs $\&$ Digraphs, third edition.Chapman $\&$ Hall, New York, 1996. MR 1408678 |
| Reference:
|
[5] G. Chartrand, O. R. Oellermann, S. Tian, H. B. Zou: Steiner distance in graphs.Čas. Pěst. Mat. 114 (1989), 399–410. MR 1027236 |
| . |
