Maximum genus, connectivity and minimal degree of graphs (Q2570108): Difference between revisions

The maximum genus of a connected graph \(G\), \(\gamma_M(G)\), is the maximum \(h\) such that \(G\) has a 2-cell imbedding in the orientable surface of genus \(h\). If the upper bound \(\gamma_M(G)\leq \lfloor\beta(G)/2\rfloor\), where \(\beta(G)= |E(G)|- |V(G)|+ 1\), is attained, then \(G\) is said to be upper imbeddable, and \textit{N. H. Xuong} [J. Comb. Theory, Ser. B 26, 217--225 (1979; Zbl 0403.05035)] showed that every 4-edge-connected graph is upper embeddable. The present authors show that, for each \(k= 1,2\), or \(3\), if \(G\) is a \(k\)-edge-connected graph of minimum degree \(\delta\), then there exists a nondecreasing function \(f(\delta)\) such that \(\gamma_M(G)\geq f(\delta)\beta(G)\); moreover, \(\lim_{\delta\to\infty} f(\delta)= 1/2\). Thus lower bounds for the maximum genus of a graph with any given connectivity increase as the minimum degree increases.