Maximum genus, connectivity, and Nebeský's theorem - Archdeacon, Dan Steven (Ars mathematica contemporanea, 2015)
We prove lower bounds on the maximum genus of a graph in terms of its connectivity and Betti number (cycle rank). These bounds are tight for all possible values of edge-connectivity and vertex-connectivity and for both simple and non-simple graphs. The use of Nebeský's characterization of maximum genus gives us both shorter proofs and a description of extremal graphs. An additional application of our method shows that the maximum genus is almost additive over the edge cuts.
Keywords: Betti number; Bettijevo število; ciklični rang; connectivity; cycle rank; maksimalni rod; maximum genus; Nebeský theorem; Nebeskýjev izrek; povezanost