Maximum genus, connectivity, and Nebeský's Theorem

Dan Archdeacon, Michal Kotrbčík, Roman Nedela, Martin Škoviera

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

Full Text:

PDF ABSTRACTS (EN/SI)


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