A tight lower bound on the maximum genus of a simplicial graph. (English) Zbl 0858.05041
Every connected simplicial graph has maximum genus at most one-half of its cycle rank [E. A. Nordhaus, B. M. Stewart, and the reviewer, J. Comb. Theory, Ser. B 11, 258-267 (1971; Zbl 0217.02204)]. In the present paper it is shown that such graphs having minimum valence at least three have maximum genus more than one-quarter of their cycle rank, and that this lower bound is tight. Examples of necklace multigraphs are given to show that both the simplicial and the minimum valence assumptions are essential. Applications are given to the average genus of simplicial graphs for which all vertices have valence at least three: average genus exceeds one-eighth of the cycle rank, and hence one-quarter of the maximum genus.
Reviewer: A.T.White (Kalamazoo)
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C35 | Extremal problems in graph theory |
Citations:
Zbl 0217.02204References:
| [1] | Chen, J., A linear time algorithm for isomorphism of graphs of bounded average genus, Lecture Notes in Computer Science, Vol. 657, 103-113 (1993) · Zbl 0790.05081 |
| [2] | Chen, J.; Gross, J. L., Limit points for average genus I. 3-connected and 2-connected simplicial graphs, J. Combin. Theory B, 55, 83-103 (1992) · Zbl 0709.05017 |
| [3] | Chen, J.; Gross, J. L., Limit points for average genus II. 2-connected non-simplicial graphs, J. Combin. Theory B, 56, 108-129 (1992) · Zbl 0776.05036 |
| [4] | Chen, J.; Gross, J. L., Kuratowski-type theorems for average genus, J. Combin. Theory B, 57, 100-121 (1993) · Zbl 0776.05037 |
| [5] | Chen, J.; Gross, J. L.; Rieper, R. G., Lower bounds for the average genus, J. Graph Theory, 19, 281-296 (1995) · Zbl 0819.05022 |
| [6] | Chen, J.; Kanchi, S. P.; Kanevsky, A., On the complexity of graph embeddings, Lecture Notes in Computer Science, Vol. 709, 234-245 (1993) · Zbl 1504.68157 |
| [7] | Furst, M. L.; Gross, J. L.; McGeoch, L. A., Finding a maximum genus graph imbedding, J. Asso. Comp. Mach., 35, 523-534 (1988) |
| [8] | Gross, J. L.; Furst, M. L., Hierarchy of imbedding-distribution invariants of a graph, J. Graph Theory, 11, 205-220 (1987) · Zbl 0643.05026 |
| [9] | Gross, J. L.; Klein, E. W.; Rieper, R. G., On the average genus of graphs, Graphs Combin., 9, 153-162 (1993) · Zbl 0777.05051 |
| [10] | Gross, J. L.; Tucker, T. W., Topological Graph Theory (1987), Wiley-Interscience: Wiley-Interscience New York · Zbl 0621.05013 |
| [11] | Jaeger, F.; Payan, C.; Xuong, N. H., Genre maximal et connectivité d’un graphe, C. R. Acad. Sc. Paris, 285, 337-337 (1977) · Zbl 0369.05027 |
| [12] | Jungerman, M., A characterization of upper embeddable graphs, Trans. Amer. Math. Soc., 241, 401-406 (1978) · Zbl 0379.05025 |
| [13] | Kanchi, S. P.; Chen, J., A tight lower bound on the maximum genus of a 2-connected simplicial graph, Manuscript (1992) |
| [14] | Kundu, S., Bounds on number of disjoint spanning trees, J. Combin. Theory B, 17, 199-203 (1974) · Zbl 0285.05113 |
| [15] | Nebeský, L., Every connected, locally connected graph is upper imbeddable, J. Graph Theory, 5, 205-207 (1981) · Zbl 0459.05036 |
| [16] | Nordhaus, E.; Ringeisen, R.; Stewart, B.; White, A., A Kuratowski-type theorem for the maximum genus of a graph, J. Combin. Theory B, 12, 260-267 (1972) · Zbl 0217.02301 |
| [17] | Nordhaus, E.; Stewart, B.; White, A., On the maximum genus of a graph, J. Combin. Theory B, 11, 258-267 (1971) · Zbl 0217.02204 |
| [18] | Payan, C.; Sakarovitch, M., Ensembles cycliquement stables et graphes cubiques, Cahiers du Centre d’Etude de Recherche Opérationnelle (Bruxelle), No. 2, 3, 4, 319-343 (1975) · Zbl 0314.05101 |
| [19] | Ringeisen, R., The maximum genus of a graph, (Ph.D. Thesis (1970), Department of Mathematics, Michigan State University) · Zbl 0373.05030 |
| [20] | Ringeisen, R., Determining all compact orientable 2-manifolds upon which \(K_{m,n}\) has 2-cell imbeddings, J. Combin. Theory B, 12, 101-104 (1972) · Zbl 0213.26002 |
| [21] | Ringeisen, R., Survey of results on the maximum genus of a graph, J. Graph Theory, 3, 1-13 (1979) · Zbl 0398.05029 |
| [22] | Skoviera, M., The maximum genus of graphs of diameter two, Discrete Math., 87, 175-180 (1991) · Zbl 0724.05021 |
| [23] | Stahl, S., Region distributions of graph embeddings and stirling numbers, Discrete Math., 82, 57-78 (1990) · Zbl 0706.05027 |
| [24] | Stahl, S., Region distributions of some small diameter graphs, Discrete Math., 89, 281-299 (1991) · Zbl 0731.05034 |
| [25] | Stahl, S., On the number of maximum genus embeddings of almost all graphs, Euro. J. Combin., 13, 119-126 (1992) · Zbl 0757.05051 |
| [26] | White, A. T., Graphs, Groups and Surfaces (1984), North-Holland: North-Holland Amsterdam · Zbl 0378.05028 |
| [27] | Xuong, N. H., How to determine the maximum genus of a graph, J. Combin. Theory B, 26, 217-225 (1979) · Zbl 0403.05035 |
| [28] | Xuong, N. H., Upper-embeddable graphs and related topics, J. Combin. Theory B, 26, 226-232 (1979) · Zbl 0403.05036 |
| [29] | Zaks, J., The maximum genus of cartesian products of graphs, Canad. J. Math., 26, 1025-1035 (1974) · Zbl 0291.05103 |
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.
