| Title:
|
Stratidistance in stratified graphs (English) |
| Author:
|
Chartrand, Gary |
| Author:
|
Gavlas, Heather |
| Author:
|
Henning, Michael A. |
| Author:
|
Rashidi, Reza |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
122 |
| Issue:
|
4 |
| Year:
|
1997 |
| Pages:
|
337-347 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
graph |
| Keyword:
|
distance center |
| Keyword:
|
periphery |
| Keyword:
|
center and periphery |
| MSC:
|
05C12 |
| idZBL:
|
Zbl 0898.05023 |
| idMR:
|
MR1489394 |
| DOI:
|
10.21136/MB.1997.126213 |
| . |
| Date available:
|
2009-09-24T21:27:06Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/126213 |
| . |
| Reference:
|
[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 1369256 |
| Reference:
|
[2] G. Chartrand L. Holley R. Rashidi, and N. A. Sherwani: Distance in stratified graphs.Preprint. |
| Reference:
|
[3] R. Rashidi: The Theory and Applications of Stratified Graphs.Ph. D. Dissertation, Western Michigan University (1994). MR 2692329 |
| . |
