Distance in stratified graphs

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 rad_XG of G and the maximum X-eccentricity is the X-diameter diam_XG. It is shown that for every three positive integers a, b and k with ab, there exist a k-stratified graph G with rad_XG = a and diam_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 rad_XG t diam_XG, there exist at least one vertex v with e_X(v) = t; while if rad_XG 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) = rad_XG and the X-periphery P_X (G) is the subgraph induced by those vertices v with e_X(G) = diam_XG. It is shown that for k-stratified graphs H₁, H₂,..., H_k with colors X₁, X₂,..., X_k and a positive integer n, there exists a k-stratified graph G such that CX_i(G) H_i (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.