Maximum genus, connectivity, and Nebeský's Theorem
Abstract
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
Maximum genus, Nebesky theorem, Betti number, cycle rank, connectivity
DOI: https://doi.org/10.26493/1855-3974.356.66e
ISSN: 1855-3974
Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications