Distance in stratified graphs

Chartrand, Gary ; Hansen, Lisa ; Rashidi, Reza ; Sherwani, Naveed

Czechoslovak Mathematical Journal, Tome 50 (2000) no. 1, pp. 35-46.

Résumé

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.

Détail

Classification : 05C12, 05C15