265 KB30 KB200820252015Archdeacon, Dan StevenKotrbčík, MichalNedela, RomanŠkoviera, Martinštevilka:1letnik:9str. 51-61COBISSID:1537209796ISSN:1855-3966URN:URN:NBN:SI:doc-UBZO1DIHenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaBetti numberBettijevo številociklični rangconnectivitycycle rankmaksimalni rodmaximum genusNebeský theoremNebeskýjev izrekpovezanostMaximum genus, connectivity, and Nebeský's theorem|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 cutsDoločimo spodnje meje za maksimalni rod grafa v smislu njegove povezanosti in Bettijevega števila (cikličnega ranga). Te meje so ostre za vse možne vrednosti povezavne-povezanosti in vozliščne-povezanosti ter veljajo tako za enostavne kot tudi ne-enostavne grafe. Uporaba Nebeskýjeve karakterizacije maksimalnega rodu nam daje ne samo krajše dokaze ampak tudi opis ekstremalnih grafov. Dodatna aplikacija naše metode pokaže, da je maksimalni rod skoraj aditiven nad povezavnimi reziTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije