Geodesic
Stratidistance in stratified graphs
Mathematica Bohemica, Tome 122 (1997) no. 4, pp. 337-347

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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\{\rho_{X_i}(v)\mid1\le i\le k\}$. 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\ge2$, 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$.
DOI : 10.21136/MB.1997.126213
Classification : 05C12
Keywords: graph; distance center; periphery; center and periphery 
Chartrand, Gary; Gavlas, Heather; Henning, Michael A.; Rashidi, Reza. Stratidistance in stratified graphs. Mathematica Bohemica, Tome 122 (1997) no. 4, pp. 337-347. doi: 10.21136/MB.1997.126213
@article{10_21136_MB_1997_126213,
     author = {Chartrand, Gary and Gavlas, Heather and Henning, Michael A. and Rashidi, Reza},
     title = {Stratidistance in stratified graphs},
     journal = {Mathematica Bohemica},
     pages = {337--347},
     year = {1997},
     volume = {122},
     number = {4},
     doi = {10.21136/MB.1997.126213},
     mrnumber = {1489394},
     zbl = {0898.05023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.1997.126213/}
}
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
SP  - 337
EP  - 347
VL  - 122
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.1997.126213/
DO  - 10.21136/MB.1997.126213
LA  - en
ID  - 10_21136_MB_1997_126213
ER  - 
%0 Journal Article
%A Chartrand, Gary
%A Gavlas, Heather
%A Henning, Michael A.
%A Rashidi, Reza
%T Stratidistance in stratified graphs
%J Mathematica Bohemica
%D 1997
%P 337-347
%V 122
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.1997.126213/
%R 10.21136/MB.1997.126213
%G en
%F 10_21136_MB_1997_126213

[1] G. Chartrand L. Eroh R. Rashidi M. Schultz, and N. A. Sherwani: Distance, stratified graphs, and greatest stratified subgraphs. Congress. Numer. 107(1995), 81-96. | MR

[2] G. Chartrand L. Holley R. Rashidi, and N. A. Sherwani: Distance in stratified graphs. Preprint.

[3] R. Rashidi: The Theory and Applications of Stratified Graphs. Ph. D. Dissertation, Western Michigan University (1994). | MR

Cité par Sources :