Geodesic
Distance in stratified graphs
Czechoslovak Mathematical Journal, Tome 50 (2000) no. 1, pp. 35-46 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

A graph $G$ is stratified if its vertex set is partitioned into classes, called strata. If there are $k$ strata, then $G$ is $k$-stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color $X$ in a stratified graph $G$, the $X$-eccentricity $e_X(v)$ of a vertex $v$ of $G$ is the distance between $v$ and an $X$-colored vertex furthest from $v$. The minimum $X$-eccentricity among the vertices of $G$ is the $X$-radius $\mathop {\mathrm rad}\nolimits _XG$ of $G$ and the maximum $X$-eccentricity is the $X$-diameter $\mathop {\mathrm diam}\nolimits _XG$. It is shown that for every three positive integers $a, b$ and $k$ with $a \le b$, there exist a $k$-stratified graph $G$ with $\mathop {\mathrm rad}\nolimits _XG=a$ and $\mathop {\mathrm diam}\nolimits _XG=b$. The number $s_X$ denotes the minimum $X$-eccetricity among the $X$-colored vertices of $G$. It is shown that for every integer $t$ with $\mathop {\mathrm rad}\nolimits _XG \le t \le \mathop {\mathrm diam}\nolimits _XG$, there exist at least one vertex $v$ with $e_X(v)=t$; while if $\mathop {\mathrm rad}\nolimits _XG \le t \le s_X$, then there are at least two such vertices. The $X$-center $C_X(G)$ is the subgraph induced by those vertices $v$ with $e_X(v)=\mathop {\mathrm rad}\nolimits _XG$ and the $X$-periphery $P_X(G)$ is the subgraph induced by those vertices $v$ with $e_X(G)=\mathop {\mathrm diam}\nolimits _XG$. It is shown that for $k$-stratified graphs $H_1, H_2, \dots , H_k$ with colors $X_1, X_2, \dots , X_k$ and a positive integer $n$, there exists a $k$-stratified graph $G$ such that $C_{X_i}(G) \cong H_i \ (1 \le i \le k)$ and $d(C_{X_i}(G), C_{X_j}(G)) \ge n \text{for} i \ne j$. Those $k$-stratified graphs that are peripheries of $k$-stratified graphs are characterized. Other distance-related topics in stratified graphs are also discussed.
A graph $G$ is stratified if its vertex set is partitioned into classes, called strata. If there are $k$ strata, then $G$ is $k$-stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color $X$ in a stratified graph $G$, the $X$-eccentricity $e_X(v)$ of a vertex $v$ of $G$ is the distance between $v$ and an $X$-colored vertex furthest from $v$. The minimum $X$-eccentricity among the vertices of $G$ is the $X$-radius $\mathop {\mathrm rad}\nolimits _XG$ of $G$ and the maximum $X$-eccentricity is the $X$-diameter $\mathop {\mathrm diam}\nolimits _XG$. It is shown that for every three positive integers $a, b$ and $k$ with $a \le b$, there exist a $k$-stratified graph $G$ with $\mathop {\mathrm rad}\nolimits _XG=a$ and $\mathop {\mathrm diam}\nolimits _XG=b$. The number $s_X$ denotes the minimum $X$-eccetricity among the $X$-colored vertices of $G$. It is shown that for every integer $t$ with $\mathop {\mathrm rad}\nolimits _XG \le t \le \mathop {\mathrm diam}\nolimits _XG$, there exist at least one vertex $v$ with $e_X(v)=t$; while if $\mathop {\mathrm rad}\nolimits _XG \le t \le s_X$, then there are at least two such vertices. The $X$-center $C_X(G)$ is the subgraph induced by those vertices $v$ with $e_X(v)=\mathop {\mathrm rad}\nolimits _XG$ and the $X$-periphery $P_X(G)$ is the subgraph induced by those vertices $v$ with $e_X(G)=\mathop {\mathrm diam}\nolimits _XG$. It is shown that for $k$-stratified graphs $H_1, H_2, \dots , H_k$ with colors $X_1, X_2, \dots , X_k$ and a positive integer $n$, there exists a $k$-stratified graph $G$ such that $C_{X_i}(G) \cong H_i \ (1 \le i \le k)$ and $d(C_{X_i}(G), C_{X_j}(G)) \ge n \text{for} i \ne j$. Those $k$-stratified graphs that are peripheries of $k$-stratified graphs are characterized. Other distance-related topics in stratified graphs are also discussed.
Classification : 05C12, 05C15 
@article{CMJ_2000_50_1_a4,
     author = {Chartrand, Gary and Hansen, Lisa and Rashidi, Reza and Sherwani, Naveed},
     title = {Distance in stratified graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {35--46},
     year = {2000},
     volume = {50},
     number = {1},
     mrnumber = {1745456},
     zbl = {1033.05031},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2000_50_1_a4/}
}
TY  - JOUR
AU  - Chartrand, Gary
AU  - Hansen, Lisa
AU  - Rashidi, Reza
AU  - Sherwani, Naveed
TI  - Distance in stratified graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2000
SP  - 35
EP  - 46
VL  - 50
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/CMJ_2000_50_1_a4/
LA  - en
ID  - CMJ_2000_50_1_a4
ER  - 
%0 Journal Article
%A Chartrand, Gary
%A Hansen, Lisa
%A Rashidi, Reza
%A Sherwani, Naveed
%T Distance in stratified graphs
%J Czechoslovak Mathematical Journal
%D 2000
%P 35-46
%V 50
%N 1
%U http://geodesic.mathdoc.fr/item/CMJ_2000_50_1_a4/
%G en
%F CMJ_2000_50_1_a4
Chartrand, Gary; Hansen, Lisa; Rashidi, Reza; Sherwani, Naveed. Distance in stratified graphs. Czechoslovak Mathematical Journal, Tome 50 (2000) no. 1, pp. 35-46. http://geodesic.mathdoc.fr/item/CMJ_2000_50_1_a4/

[1] H. Bielak, M. M. Syslo: Peripheral vertices in graphs. Studia Sci. Math. Hungar. 18 (1983), 269–275. | MR

[2] F. Buckley, Z. Miller, P. J. Slater: On graphs containing a given graph as center. J. Graph Theory 5 (1981), 427–434. | DOI | MR

[3] H. Choi, K. Nakajima, C. S. Rim: Graph bipartization and via minimization. SIAM J. Discrete Math. 2 (1989), 38–47. | DOI | MR

[4] F. Harary, R. Z. Norman: The dissimilarity characteristic of Husimi trees. Ann. Math. 58 (1953), 134–141. | DOI | MR

[5] L. Lesniak: Eccentric sequences in graph. Period. Math. Hungar 6 (1975), 287–293. | DOI | MR

[6] P. A. Ostrand: Graphs with specified radius and diameter. Discrete Math. 4 (1973), 71–75. | DOI | MR | Zbl

[7] R. Rashidi: The Theory and Applications of Stratified Graphs. Ph.D. Dissertation, Western Michigan University, 1994.

[8] M. Sarrafzadeh, D. T. Lee: A new approach to topological via minimization. IEEE Transactions on Computer-Aided Design 8 (1989), 890–900. | DOI

[9] N. A. Sherwani: A Graph Theoretic Approach to Single Row Routing Problems. Ph.D. Thesis, University of Nebraska, 1988.

[10] N. A. Sherwani, J. S. Deogun: New lower bound for single row routing problems. Proceedings of 1989 IEEE Midwest Symposium on Circuits and Systems, August 14–15, 1989, Urbana-Champaign, IL.

[11] N. A. Sherwani: Algorithms for VLSI Physical Design Automation. Kluwer, 1993.