Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
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.
References:
[1] H. Bielak, M. M. Syslo: Peripheral vertices in graphs. Studia Sci. Math. Hungar. 18 (1983), 269–275. MR 0787932
[2] F. Buckley, Z. Miller, P. J. Slater: On graphs containing a given graph as center. J. Graph Theory 5 (1981), 427–434. DOI 10.1002/jgt.3190050413 | MR 0635706
[3] H. Choi, K. Nakajima, C. S. Rim: Graph bipartization and via minimization. SIAM J. Discrete Math. 2 (1989), 38–47. DOI 10.1137/0402004 | MR 0976786
[4] F. Harary, R. Z. Norman: The dissimilarity characteristic of Husimi trees. Ann. Math. 58 (1953), 134–141. DOI 10.2307/1969824 | MR 0055693
[5] L. Lesniak: Eccentric sequences in graph. Period. Math. Hungar 6 (1975), 287–293. DOI 10.1007/BF02017925 | MR 0406872
[6] P. A. Ostrand: Graphs with specified radius and diameter. Discrete Math. 4 (1973), 71–75. DOI 10.1016/0012-365X(73)90116-7 | MR 0313126 | Zbl 0265.05123
[7] R. Rashidi: The Theory and Applications of Stratified Graphs. Ph.D. Dissertation, Western Michigan University, 1994.
[8] M. Sarrafzadeh, D. T. Lee: A new approach to topological via minimization. IEEE Transactions on Computer-Aided Design 8 (1989), 890–900. DOI 10.1109/43.31548
[9] N. A. Sherwani: A Graph Theoretic Approach to Single Row Routing Problems. Ph.D. Thesis, University of Nebraska, 1988.
[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.
[11] N. A. Sherwani: Algorithms for VLSI Physical Design Automation. Kluwer, 1993.
Search
Partner of
