Distance in stratified graphs |
| |
Authors: | Gary Chartrand Lisa Hansen Reza Rashidi Naveed Sherwani |
| |
Affiliation: | (1) Western Michigan University, Kalamazoo, MI, 49008, U.S.A.;(2) Design Technology, Intel Corporation, Beaverton, OR, 97006, U.S.A. |
| |
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 eX(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 radXG of G and the maximum X-eccentricity is the X-diameter diamXG. It is shown that for every three positive integers a, b and k with a b, there exist a k-stratified graph G with radXG = a and diamXG = b. The number sX denotes the minimum X-eccetricity among the X-colored vertices of G. It is shown that for every integer t with radXG t diamXG, there exist at least one vertex v with eX(v) = t; while if radXG t sX, then there are at least two such vertices. The X-center CX(G) is the subgraph induced by those vertices v with eX(v) = radXG and the X-periphery PX (G) is the subgraph induced by those vertices v with eX(G) = diamXG. It is shown that for k-stratified graphs H1, H2,..., Hk with colors X1, X2,..., Xk and a positive integer n, there exists a k-stratified graph G such that CXi(G) Hi (1 ; i ; k1) and 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|