Distance in stratified graphs

Title:

Distance in stratified graphs

Creator:

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

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:c3c6f2e2-b264-4940-8e7e-91f364f25c4f
uuid:c3c6f2e2-b264-4940-8e7e-91f364f25c4f

Subject:

math, graphs, and strata in a stratified graph

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

35-43

Source:

Czechoslovak Mathematical Journal | 2000 Volume:50 | Number:1

Harvested from:

CDK

Metadata only:

false