A Genus Inequality of The Union Graphs

Abstract

The genus of a graph \(G\), denoted by \(\gamma(G)\), is the minimum genus of an orientable surface in which the graph can be embedded. In the paper, we use the Joint Tree Model to immerse a graph on the plane and obtain an associated polygon of the graph. Along the way, we construct a genus embedding of the edge disjoint union of \(K\) and \(H\), and solve Michael Stiebitz’s proposed conjecture: Let \(G\) be the edge disjoint union of a complete graph \(K\) and an arbitrary graph \(H\). Let \(H’\) be the graph obtained from \(H\) by contracting the set \(V(X)\) to a single vertex. Then

\[\gamma(K) + \gamma(H’) \leq \gamma(G).\]