| Title:
|
Distance in stratified graphs (English) |
| Author:
|
Chartrand, Gary |
| Author:
|
Hansen, Lisa |
| Author:
|
Rashidi, Reza |
| Author:
|
Sherwani, Naveed |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
50 |
| Issue:
|
1 |
| Year:
|
2000 |
| Pages:
|
35-46 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| MSC:
|
05C12 |
| MSC:
|
05C15 |
| idZBL:
|
Zbl 1033.05031 |
| idMR:
|
MR1745456 |
| . |
| Date available:
|
2009-09-24T10:29:35Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127545 |
| . |
| Reference:
|
[1] H. Bielak, M. M. Syslo: Peripheral vertices in graphs.Studia Sci. Math. Hungar. 18 (1983), 269–275. MR 0787932 |
| Reference:
|
[2] F. Buckley, Z. Miller, P. J. Slater: On graphs containing a given graph as center.J. Graph Theory 5 (1981), 427–434. MR 0635706, 10.1002/jgt.3190050413 |
| Reference:
|
[3] H. Choi, K. Nakajima, C. S. Rim: Graph bipartization and via minimization.SIAM J. Discrete Math. 2 (1989), 38–47. MR 0976786, 10.1137/0402004 |
| Reference:
|
[4] F. Harary, R. Z. Norman: The dissimilarity characteristic of Husimi trees.Ann. Math. 58 (1953), 134–141. MR 0055693, 10.2307/1969824 |
| Reference:
|
[5] L. Lesniak: Eccentric sequences in graph.Period. Math. Hungar 6 (1975), 287–293. MR 0406872, 10.1007/BF02017925 |
| Reference:
|
[6] P. A. Ostrand: Graphs with specified radius and diameter.Discrete Math. 4 (1973), 71–75. Zbl 0265.05123, MR 0313126, 10.1016/0012-365X(73)90116-7 |
| Reference:
|
[7] R. Rashidi: The Theory and Applications of Stratified Graphs.Ph.D. Dissertation, Western Michigan University, 1994. |
| Reference:
|
[8] M. Sarrafzadeh, D. T. Lee: A new approach to topological via minimization.IEEE Transactions on Computer-Aided Design 8 (1989), 890–900. 10.1109/43.31548 |
| Reference:
|
[9] N. A. Sherwani: A Graph Theoretic Approach to Single Row Routing Problems.Ph.D. Thesis, University of Nebraska, 1988. |
| Reference:
|
[10] N. A. Sherwani, J. S. Deogun: 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. |
| Reference:
|
[11] N. A. Sherwani: Algorithms for VLSI Physical Design Automation.Kluwer, 1993. |
| . |
