×

The orientable genus of some joins of complete graphs with large edgeless graphs. (English) Zbl 1182.05042

The authors investigate the orientable genus of the join of a complete graph \(K_n\) with a large edgeless graph \(\overline{K_m}\). Concretely, they show that the genus of \(\overline{K_m}+K_n\) is equal to that of the complete bipartite graph \(K_{m,n}\) if \(n\) is even and \(m \geq n\). Also it is shown that the quality holds when \(n=2^p+2, p\geq 3\) and \(m\geq n-1\), or when \(n=2^p+1, p\geq 3\) and \(m\geq n+1\).

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bouchet, A., Orientable and nonorientable genus of the complete bipartite graph, J. Combin. Theory Ser. B, 24, 24-33 (1978) · Zbl 0311.05104
[2] David L. Craft, Surgical techniques for constructing minimal orientable imbeddings of joins and compositions of graphs, Ph.D. Thesis, Western Michigan University, 1991; David L. Craft, Surgical techniques for constructing minimal orientable imbeddings of joins and compositions of graphs, Ph.D. Thesis, Western Michigan University, 1991
[3] Craft, David L., On the genus of joins and compositions of graphs, Discrete Math., 178, 25-50 (1998) · Zbl 0888.05021
[4] Ellingham, M. N.; Stephens, Chris, The nonorientable genus of joins of complete graphs with large edgeless graphs, J. Combin. Theory Ser. B, 97, 827-845 (2007) · Zbl 1122.05028
[5] Ellingham, M. N.; Stephens, Chris; Zha, Xiaoya, Counterexamples to the nonorientable genus conjecture for complete tripartite graphs, European J. Combin., 26, 387-399 (2005) · Zbl 1060.05025
[6] Ellingham, M. N.; Stephens, Chris; Zha, Xiaoya, The nonorientable genus of complete tripartite graphs, J. Combin. Theory Ser. B, 96, 529-559 (2006) · Zbl 1097.05014
[7] Grannell, Mike J.; Griggs, Terry S.; Širáň, Jozef, Hamiltonian embeddings from triangulations, Bull. London Math. Soc., 39, 447-452 (2007) · Zbl 1123.05032
[8] Gross, J. L.; Tucker, T. W., Topological Graph Theory (1987), Wiley Interscience: Wiley Interscience New York, (Republished by Dover, Mineola, New York, 2001) · Zbl 0621.05013
[9] Jungerman, M., Orientable triangular embeddings of \(K_{18} - K_3\) and \(K_{13} - K_3\), J. Combin. Theory Ser. B, 16, 293-294 (1974) · Zbl 0277.05108
[10] Kawarabayashi, Ken-ichi; Stephens, Chris; Zha, Xiaoya, Orientable and nonorientable genera of some complete tripartite graphs, SIAM J. Discrete Math., 18, 479-487 (2004) · Zbl 1069.05026
[11] Korzhik, Vladimir P., Triangular embeddings of \(K_n - K_m\) with unboundedly large \(m\), Discrete Math., 190, 149-162 (1998) · Zbl 0958.05039
[12] Magajna, Z.; Mohar, B.; Pisanski, T., Minimal ordered triangulations of surfaces, J. Graph Theory, 10, 451-460 (1986) · Zbl 0651.05031
[13] Mohar, B.; Parsons, T. D.; Pisanski, T., The genus of nearly complete bipartite graphs, Ars Combin., 20B, 173-183 (1985) · Zbl 0586.05017
[14] Mohar, Bojan; Thomassen, Carsten, Graphs on Surfaces (2001), Johns Hopkins University Press: Johns Hopkins University Press Baltimore · Zbl 0979.05002
[15] Ringel, G., Der vollständige paare Graph auf nichtorientierbaren Flächen, J. Reine Angew. Math., 220, 88-93 (1965) · Zbl 0132.21204
[16] Ringel, G., Das Geschlecht des vollständigen paaren Graphen, Abh. Math. Sem. Univ. Hamburg, 28, 139-150 (1965) · Zbl 0132.21203
[17] Ringel, G., Map Color Theorem (1974), Springer-Verlag: Springer-Verlag Berlin · Zbl 0287.05102
[18] Ringel, G.; Youngs, J. W.T., Das Geschlecht des symmetrischen vollständigen dreifarbbaren Graphen, Comment. Math. Helv., 45, 152-158 (1970) · Zbl 0192.60507
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.