A New Bound on Maximum Genus of Simple Graphs

Abstract

Let \(G\) be a connected simple graph with girth \(g\) and minimal degree \(\delta \geq 3\). If \(G\) is not up-embeddable, then, when \(G\) is 1-edge connected,

\[\gamma_M(G) \geq \frac{D_1(\delta,g)-2}{2D_1(\delta,g)-1}\beta(G)+ \frac{D_1(\delta,g)+1}{2D_1(\delta,g)-1}.\]

When \(G\) is \(k\)(\(k = 2, 3\))-edge connected ,

\[\gamma_M(G) \geq \frac{D_k(\delta,g)-1}{2D_k(\delta,g)}\beta(G)+ \frac{D_k(\delta,g)+1}{2D_k(\delta,g)}.\]

The functions \(D_k(\delta, g)\) (\(k = 1, 2, 3\)) are increasing functions on \(\delta\) and \(g\).