Seminár z teórie grafov - Martin Škoviera (17.3.2022)
vo štvrtok 17.3.2022 o 9:50 hod. v miestnosti M/213
Prednášajúci: Martin Škoviera
Názov: Cyclic connectivity, edge-elimination, the twisted Isaacs graphs, and beyond
Termín: 17.3.2022, 9:50 hod., M 213
Abstrakt:
Edge-elimination is an operation of removing an edge together with its end-vertices. We study the effect of this operation on the cyclic connectivity of a cubic graph. Disregarding a small number of cubic graphs with no more than six vertices, this operation cannot decrease cyclic connectivity by more than two. We show that apart from three exceptional graphs (the cube, the twisted cube, and the Petersen graph) every 2-connected cubic graph on at least eight vertices contains an edge whose elimination decreases cyclic connectivity by at most one. A substantial ingredient of the proof is a theorem that provides a structural characterisation of Isaacs flower snarks and their natural generalisation, twisted Isaacs graphs.
We explain how the result is related to several other problems concerning cubic graphs, for example, the existence of long cycles, decycling, and maximum genus embeddings of cubic graphs into surfaces. This is a joint work with Roman Nedela.