Maximum genus and connectivity (Q1910565): Difference between revisions

The authors show that the tight lower bound for the maximum genus of a 2-edge-connected simplicial graph is \(\lceil \beta(G)/3\rceil\), where \(\beta(G)\) is the cycle rank of graph \(G\). This compares with the well-known tight upper bound \(\lfloor \beta(G)/2\rfloor\), for arbitrary connected graphs \(G\). They develop a general method for constructing 3-vertex-connected graphs which attain the lower bound above; in combination with results of Chen, Kanchi, and Gross (Discrete Math., to appear) and of Kanchi and Chen (Manuscript, 1992), the new results give a complete picture of the tight lower bounds for the maximum genus of simplicial graphs. \textit{S. Kundu} [J. Comb. Theory, Ser. B 17, 199-203 (1974; Zbl 0285.05113)] and \textit{N. H. Zuong} [J. Comb. Theory, Ser. B 26, 217-225 (1979; Zbl 0403.05035)] showed that the upper bound above is attained, for all 4-vertex-connected (or 4-edge-connected) graphs.