A tight lower bound on the maximum genus of a simplicial graph (Q1923508): Difference between revisions

Every connected simplicial graph has maximum genus at most one-half of its cycle rank [\textit{E. A. Nordhaus}, \textit{B. M. Stewart}, and the reviewer, J. Comb. Theory, Ser. B 11, 258-267 (1971; Zbl 0217.02204)]. In the present paper it is shown that such graphs having minimum valence at least three have maximum genus more than one-quarter of their cycle rank, and that this lower bound is tight. Examples of necklace multigraphs are given to show that both the simplicial and the minimum valence assumptions are essential. Applications are given to the average genus of simplicial graphs for which all vertices have valence at least three: average genus exceeds one-eighth of the cycle rank, and hence one-quarter of the maximum genus.