Overlap matrices and total imbedding distributions. (English) Zbl 0798.05017
For a given graph \(G\), let \(\alpha_ g(G)\), \(g= 0,1,2,\dots\), denote the number of homeomorphically different 2-cell embeddings of \(G\) in a surface of genus \(g\). The sequence \(\alpha_ g(G)\), \(g=0,1,2,\dots\), is the genus distribution of \(G\). This concept can be extended to include nonorientable embeddings. The authors determine the extended embedding distributions for several classes of graphs. The computations in the nonorientable case are done by applying a theorem of the reviewer [An obstruction to embedding graphs in surfaces, Discrete Math. 78, No. 1/2, 135-142 (1989; Zbl 0686.05019)] that relates the topological types of embedding surfaces to ranks of the corresponding overlap matrices.
Reviewer: B.Mohar (Ljubljana)
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
Citations:
Zbl 0686.05019References:
| [1] | Broida, J. G.; Williamson, S. G., Comprehensive Introduction to Linear Algebra (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0683.15001 |
| [2] | Chen, J., The distribution of graph imbeddings on topological surfaces, (Ph.D. Thesis (1990), Department of Mathematics, Columbia University: Department of Mathematics, Columbia University NY) |
| [3] | Chen, J.; Gross, J. L., Limit points for average genus (I). 3-connected and 2-connected simplical graphs, J. Combin. Theory Ser. B, 55, 83-103 (1992) · Zbl 0709.05017 |
| [4] | Chen, J.; Gross, J. L., Limit points for average genus (II). 2-connected non-simplicial graphs, J. Combin. Theory Ser. B, 56, 108-129 (1992) · Zbl 0776.05036 |
| [5] | Chen, J.; Gross, J. L., Kuratowski-type theorems for average genus, J. Combin. Theory Ser. B, 57, 100-121 (1993) · Zbl 0776.05037 |
| [6] | Edmonds, J., On the surface duality of linear graphs, J. Res. Nat. Bur. Standards Sect. B, 121-123 (1965) · Zbl 0132.20604 |
| [7] | Furst, M. L.; Gross, J. L.; Statman, R., Genus distributions for two classes of graphs, J. Combin. Theory Ser. B, 46, 22-36 (1989) · Zbl 0669.05028 |
| [8] | Gross, J. L.; Furst, M. L., Hierarchy for imbedding-distribution invariants of a graph, J. Graph Theory, 11-14, 205-220 (1987) · Zbl 0643.05026 |
| [9] | J.L. Gross, E.W. Klein and R.G. Rieper, On the average genus of a graph, Graphs and Combin., to appear.; J.L. Gross, E.W. Klein and R.G. Rieper, On the average genus of a graph, Graphs and Combin., to appear. · Zbl 0777.05051 |
| [10] | Gross, J. L.; Robbins, D. P.; Tucker, T. W., Genus distributions for bouquets of circles, J. Combin. Theory Ser. B, 47, 292-306 (1989) · Zbl 0688.05038 |
| [11] | Gross, J. L.; Tucker, T. W., Topological Graph Theory (1987), Wiley-Interscience: Wiley-Interscience New York · Zbl 0621.05013 |
| [12] | Lang, S., Algebra (1984), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0712.00001 |
| [13] | McGeoch, L. A., Algorithms for two graph problems: computing maximum-genus imbeddings and the two-server problem, (Ph.D. Thesis (1987), Computer Science Dept., Carnegie Mellon University: Computer Science Dept., Carnegie Mellon University PA) |
| [14] | Mohar, B., An obstruction to embedding graphs in surfaces, Discrete Math., 78, 135-142 (1989) · Zbl 0686.05019 |
| [15] | Rieper, R. G., The enumeration of graph imbeddings, (Ph.D. Thesis (1987), Dept. of Mathematics, Western Michigan University: Dept. of Mathematics, Western Michigan University Kalamazoo, MI) |
| [16] | White, A. T., Graphs, Groups and Surfaces (1984), North-Holland: North-Holland Amsterdam · Zbl 0378.05028 |
| [17] | Xuong, N. H., How to determine the maximum genus of a graph, J. Combin. Theory Ser. B, 26, 216-225 (1979) · Zbl 0403.05035 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
