On the connectivity of graphs embedded in surfaces (Q1272478)

Let \(S\) be a closed 2-manifold (a surface), either orientable or nonorientable. The authors define the maximum connectivity of \(S\), \(\kappa_{\max}(S)\), to be the maximum connectivity among all graphs imbeddable in \(S\); the genus connectivity \(\kappa_{\text{gen}}(S)\) is the maximum connectivity among all graphs which are genus imbeddable in \(S\). Clearly \(\kappa_{\text{gen}}(S)\leq \kappa_{\max}(S)\). Let \(S\) be in class A (respectively class B) if equality holds (does not hold). Work of \textit{R. J. Cook} [Mathematika, London 20, 201-207 (1973; Zbl 0286.05107)], combined with the Ringel-Youngs solution to the Heawood map coloring problem (see, for example, \textit{G. Ringel} [Map color theorem, Springer-Verlag (1974; Zbl 0287.05102)]), shows that \(\kappa_{\max}(S)\) is one less than the Heawood number, for each surface \(S\) other than the sphere or the Klein bottle, and that the number is attained by a complete graph. The authors study the uniqueness of graphs attaining connectivity \(\kappa_{\max}(S)\). Then they show that, for \(n\geq 30\), the interval \([\gamma(K_n)+1, \gamma(K_{n+ 1})]\) contains the genus of at least one orientable surface in class B, and can be written as the union of two subintervals, the lower (respectively upper) subinterval containing only genera of class B (class A) surfaces. Similar results are established for \(S\) nonorientable. The location of the ``breaking point'' between these two subintervals is investigated, both for \(S\) orientable and for \(S\) nonorientable.