Distance in stratified graphs

Gary Chartrand; Lisa Hansen; Reza Rashidi; Naveed Sherwani

Czechoslovak Mathematical Journal (2000)

  • Volume: 50, Issue: 1, page 35-46
  • ISSN: 0011-4642

Abstract

top
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 r a d X G of G and the maximum X -eccentricity is the X -diameter d i a m X G . It is shown that for every three positive integers a , b and k with a ≤ b , there exist a k -stratified graph G with r a d X G = a and d i a m X G = 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 r a d X G ≤ t ≤ d i a m X G , there exist at least one vertex v with e X ( v ) = t ; while if r a d X G ≤ t ≤ 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 ) = r a d X G and the X -periphery P X ( G ) is the subgraph induced by those vertices v with e X ( G ) = d i a m X G . It is shown that for k -stratified graphs H 1 , H 2 , ⋯ , H k with colors X 1 , X 2 , ⋯ , X k and a positive integer n , there exists a k -stratified graph G such that C X i ( G ) ≅ H i ( 1 ≤ i ≤ k ) and d ( C X i ( G ) , C X j ( G ) ) ≥ n for i ≠ j . Those k -stratified graphs that are peripheries of k -stratified graphs are characterized. Other distance-related topics in stratified graphs are also discussed.

How to cite

top

Chartrand, Gary, et al. "Distance in stratified graphs." Czechoslovak Mathematical Journal 50.1 (2000): 35-46. <http://eudml.org/doc/30538>.

@article{Chartrand2000,
abstract = {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 \{r\}ad\}\nolimits _XG$ of $G$ and the maximum $X$-eccentricity is the $X$-diameter $\mathop \{\mathrm \{d\}iam\}\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 \{r\}ad\}\nolimits _XG=a$ and $\mathop \{\mathrm \{d\}iam\}\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 \{r\}ad\}\nolimits _XG \le t \le \mathop \{\mathrm \{d\}iam\}\nolimits _XG$, there exist at least one vertex $v$ with $e_X(v)=t$; while if $\mathop \{\mathrm \{r\}ad\}\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 \{r\}ad\}\nolimits _XG$ and the $X$-periphery $P_X(G)$ is the subgraph induced by those vertices $v$ with $e_X(G)=\mathop \{\mathrm \{d\}iam\}\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.},
author = {Chartrand, Gary, Hansen, Lisa, Rashidi, Reza, Sherwani, Naveed},
journal = {Czechoslovak Mathematical Journal},
keywords = {stratified graph; stratum; -radius; -diameter; -center},
language = {eng},
number = {1},
pages = {35-46},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Distance in stratified graphs},
url = {http://eudml.org/doc/30538},
volume = {50},
year = {2000},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 50
IS - 1
SP - 35
EP - 46
AB - 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 {r}ad}\nolimits _XG$ of $G$ and the maximum $X$-eccentricity is the $X$-diameter $\mathop {\mathrm {d}iam}\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 {r}ad}\nolimits _XG=a$ and $\mathop {\mathrm {d}iam}\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 {r}ad}\nolimits _XG \le t \le \mathop {\mathrm {d}iam}\nolimits _XG$, there exist at least one vertex $v$ with $e_X(v)=t$; while if $\mathop {\mathrm {r}ad}\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 {r}ad}\nolimits _XG$ and the $X$-periphery $P_X(G)$ is the subgraph induced by those vertices $v$ with $e_X(G)=\mathop {\mathrm {d}iam}\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.
LA - eng
KW - stratified graph; stratum; -radius; -diameter; -center
UR - http://eudml.org/doc/30538
ER -

References

top
  1. Peripheral vertices in graphs, Studia Sci. Math. Hungar. 18 (1983), 269–275. (1983) MR0787932
  2. 10.1002/jgt.3190050413, J. Graph Theory 5 (1981), 427–434. (1981) MR0635706DOI10.1002/jgt.3190050413
  3. 10.1137/0402004, SIAM J. Discrete Math. 2 (1989), 38–47. (1989) MR0976786DOI10.1137/0402004
  4. 10.2307/1969824, Ann. Math. 58 (1953), 134–141. (1953) MR0055693DOI10.2307/1969824
  5. 10.1007/BF02017925, Period. Math. Hungar 6 (1975), 287–293. (1975) MR0406872DOI10.1007/BF02017925
  6. 10.1016/0012-365X(73)90116-7, Discrete Math. 4 (1973), 71–75. (1973) Zbl0265.05123MR0313126DOI10.1016/0012-365X(73)90116-7
  7. The Theory and Applications of Stratified Graphs, Ph.D. Dissertation, Western Michigan University, 1994. (1994) 
  8. 10.1109/43.31548, IEEE Transactions on Computer-Aided Design 8 (1989), 890–900. (1989) DOI10.1109/43.31548
  9. A Graph Theoretic Approach to Single Row Routing Problems, Ph.D. Thesis, University of Nebraska, 1988. (1988) 
  10. 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. Algorithms for VLSI Physical Design Automation, Kluwer, 1993. (1993) 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.