On k -strong distance in strong digraphs

Ping Zhang

Mathematica Bohemica (2002)

  • Volume: 127, Issue: 4, page 557-570
  • ISSN: 0862-7959

Abstract

top
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 2 and a vertex v of a strong digraph D , the k -strong eccentricity s e 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 s r a d 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 s r a d k ( D ) ( k ( D ) ). It is shown that, for each integer k 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 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.

How to cite

top

Zhang, Ping. "On $k$-strong distance in strong digraphs." Mathematica Bohemica 127.4 (2002): 557-570. <http://eudml.org/doc/249029>.

@article{Zhang2002,
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 \ge 2$ and a vertex $v$ of a strong digraph $D$, the $k$-strong eccentricity $\mathop \{\mathrm \{s\}e\}_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 \{s\}rad\}_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 \{s\}rad\}_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.},
author = {Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {strong distance; strong eccentricity; strong center; strong periphery; strong distance; strong eccentricity; strong center; strong periphery},
language = {eng},
number = {4},
pages = {557-570},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On $k$-strong distance in strong digraphs},
url = {http://eudml.org/doc/249029},
volume = {127},
year = {2002},
}

TY - JOUR
AU - Zhang, Ping
TI - On $k$-strong distance in strong digraphs
JO - Mathematica Bohemica
PY - 2002
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 127
IS - 4
SP - 557
EP - 570
AB - 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 {s}e}_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 {s}rad}_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 {s}rad}_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.
LA - eng
KW - strong distance; strong eccentricity; strong center; strong periphery; strong distance; strong eccentricity; strong center; strong periphery
UR - http://eudml.org/doc/249029
ER -

NotesEmbed ?

top

You must be logged in to post comments.