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
    0 references
    0 references
    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

    Identifiers