The nonorientable genus of complete tripartite graphs (Q2496204)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The nonorientable genus of complete tripartite graphs |
scientific article |
Statements
The nonorientable genus of complete tripartite graphs (English)
0 references
12 July 2006
0 references
\textit{S. Stahl} and the reviewer [Discrete Math. 14, 279--296 (1976; Zbl 0332.05105)] conjectured that the nonorientable genus of the complete tripartite graph \(K_{a,b,c}\), where \(a\geq b\geq c\), is \(\lceil(a-2)(b+c-2)/2\rceil\). The present authors [Eur. J. Comb. 26, 387--399 (2005; Zbl 1060.05025)] showed that each of \(K_{3,3,3}\), \(K_{4,4,1}\), and \(K_{4,4,3}\) is a counterexample to that conjecture. In the present paper, they show that the conjecture holds for all other cases, and that in each of the three exceptions, the genus is exactly 1 more than the general value, thereby completing the nonorientable genus determination for complete tripartite graphs. Their clever constructions use transitions graphs, which are closely related to voltage graphs: a transition graph is the medial graph of an imbedded voltage graph.
0 references
graph embedding
0 references