zbMATH — the first resource for mathematics

Distance in stratified graphs. (English) Zbl 1033.05031
A stratified graph is an ordered pair \((G,S)\), where \(G\) is an undirected graph and \(S\) is a partition of its vertex set \(V(G)\) into classes called strata. For any stratum \(X\) the concepts analogous to the basic concepts concerning distance may be defined, namely \(X\)-eccentricity, \(X\)-radius, \(X\)-diameter, \(X\)-center, \(X\)-periphery. These concepts are studied in the paper. The study of stratified graphs is motivated on the one hand by VLSI designs, on the other hand by needs of sociology and politology.

05C12 Distance in graphs
05C15 Coloring of graphs and hypergraphs
Full Text: DOI EuDML
[1] H. Bielak, M. M. Syslo: Peripheral vertices in graphs. Studia Sci. Math. Hungar. 18 (1983), 269-275. · Zbl 0569.05030
[2] F. Buckley, Z. Miller, P. J. Slater: On graphs containing a given graph as center. J. Graph Theory 5 (1981), 427-434. · Zbl 0449.05056
[3] H. Choi, K. Nakajima, C. S. Rim: Graph bipartization and via minimization. SIAM J. Discrete Math. 2 (1989), 38-47. · Zbl 0677.68036
[4] F. Harary, R. Z. Norman: The dissimilarity characteristic of Husimi trees. Ann. Math. 58 (1953), 134-141. · Zbl 0051.40502
[5] L. Lesniak: Eccentric sequences in graph. Period. Math. Hungar 6 (1975), 287-293. · Zbl 0363.05053
[6] P. A. Ostrand: Graphs with specified radius and diameter. Discrete Math. 4 (1973), 71-75. · 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. · Zbl 05449519
[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. · Zbl 0840.68060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.