Stratidistance in stratified graphs

Chartrand, Gary, et al. "Stratidistance in stratified graphs." Mathematica Bohemica 122.4 (1997): 337-347. <http://eudml.org/doc/248136>.

@article{Chartrand1997,
abstract = {A graph $G$ is a stratified graph if its vertex set is partitioned into classes (each of which is a stratum or a color class). A stratified graph with $k$ strata is $k$-stratified. If $G$ is a connected $k$-stratified graph with strata $S_i$$(1\le i\le k)$ where the vertices of $S_i$ are colored $X_i$$(1\le i\le k)$, then the $X_i$-proximity $\rho _\{X_i\} (v)$ of a vertex $v$ of $G$ is the distance between $v$ and a vertex of $S_i$ closest to $v$. The strati-eccentricity $ se(v)$ of $v$ is $\max \lbrace \rho _\{X_i\}(v)\mid 1\le i\le k\rbrace $. The minimum strati-eccentricity over all vertices of $G$ is the stratiradius $ sr(G)$ of $G$; while the maximum strati-eccentricity is its stratidiameter $ sd(G)$. For positive integers $a,b,k$ with $a\le b$, the problem of determining whether there exists a $k$-stratified graph $G$ with $ sr(G)=a$ and $ sd(G)=b$ is investigated. A vertex $v$ in a connected stratified graph $G$ is called a straticentral vertex if $ se(v)= sr(G)$. The subgraph of $G$ induced by the straticentral vertices of $G$ is called the straticenter of $G$. It is shown that every $\ell $-stratified graph is the straticenter of some $k$-stratified graph. Next a stratiperipheral vertex $v$ of a connected stratified graph $G$ has $ se(v)= sd(G)$ and the subgraph of $G$ induced by the stratiperipheral vertices of $G$ is called the stratiperiphery of $G$. Almost every stratified graph is the stratiperiphery of some $k$-stratified graph. Also, it is shown that for a $k_1$-stratified graph $H_1$, a $k_2$-stratified graph $H_2$, and an integer $n\ge 2$, there exists a $k$-stratified graph $G$ such that $H_1$ is the straticenter of $G$, $H_2$ is the stratiperiphery of $G$, and $d(H_1,H_2)=n$.},
author = {Chartrand, Gary, Gavlas, Heather, Henning, Michael A., Rashidi, Reza},
journal = {Mathematica Bohemica},
keywords = {graph; distance center; periphery; center and periphery; graph; distance center; periphery},
language = {eng},
number = {4},
pages = {337-347},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Stratidistance in stratified graphs},
url = {http://eudml.org/doc/248136},
volume = {122},
year = {1997},
}

TY - JOUR
AU - Chartrand, Gary
AU - Gavlas, Heather
AU - Henning, Michael A.
AU - Rashidi, Reza
TI - Stratidistance in stratified graphs
JO - Mathematica Bohemica
PY - 1997
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 122
IS - 4
SP - 337
EP - 347
AB - A graph $G$ is a stratified graph if its vertex set is partitioned into classes (each of which is a stratum or a color class). A stratified graph with $k$ strata is $k$-stratified. If $G$ is a connected $k$-stratified graph with strata $S_i$$(1\le i\le k)$ where the vertices of $S_i$ are colored $X_i$$(1\le i\le k)$, then the $X_i$-proximity $\rho _{X_i} (v)$ of a vertex $v$ of $G$ is the distance between $v$ and a vertex of $S_i$ closest to $v$. The strati-eccentricity $ se(v)$ of $v$ is $\max \lbrace \rho _{X_i}(v)\mid 1\le i\le k\rbrace $. The minimum strati-eccentricity over all vertices of $G$ is the stratiradius $ sr(G)$ of $G$; while the maximum strati-eccentricity is its stratidiameter $ sd(G)$. For positive integers $a,b,k$ with $a\le b$, the problem of determining whether there exists a $k$-stratified graph $G$ with $ sr(G)=a$ and $ sd(G)=b$ is investigated. A vertex $v$ in a connected stratified graph $G$ is called a straticentral vertex if $ se(v)= sr(G)$. The subgraph of $G$ induced by the straticentral vertices of $G$ is called the straticenter of $G$. It is shown that every $\ell $-stratified graph is the straticenter of some $k$-stratified graph. Next a stratiperipheral vertex $v$ of a connected stratified graph $G$ has $ se(v)= sd(G)$ and the subgraph of $G$ induced by the stratiperipheral vertices of $G$ is called the stratiperiphery of $G$. Almost every stratified graph is the stratiperiphery of some $k$-stratified graph. Also, it is shown that for a $k_1$-stratified graph $H_1$, a $k_2$-stratified graph $H_2$, and an integer $n\ge 2$, there exists a $k$-stratified graph $G$ such that $H_1$ is the straticenter of $G$, $H_2$ is the stratiperiphery of $G$, and $d(H_1,H_2)=n$.
LA - eng
KW - graph; distance center; periphery; center and periphery; graph; distance center; periphery
UR - http://eudml.org/doc/248136
ER -