Counting circuit double covers
Autoři
Hušek, R.; Šámal, R.
Rok
2025
Publikováno
Journal of Graph Theory. 2025, 108(2), 374-395. ISSN 0364-9024.
Typ
Článek
Pracoviště
Anotace
We study a counting version of Cycle Double Cover Conjecture. We discuss why it is more interesting to count circuits (i.e., graphs isomorphic to C_k for some k) instead of cycles (graphs with all degrees even). We give an almost-exponential lower bound for graphs with a surface embedding of representativity at least 4. We also prove an exponential lower bound for planar graphs. We conjecture that any bridgeless cubic graph has at least 2^(n/2 - 1) circuit double covers and we show an infinite class of graphs for which this bound is tight.
Group connectivity: Z4 vs Z22
Autoři
Hušek, R.; Mohelníková, L.; Šámal, R.
Rok
2020
Publikováno
Journal of Graph Theory. 2020, 93(3), ISSN 0364-9024.
Homomorphisms of Cayley Graphs and Cycle Double Covers
Autoři
Hušek, R.; Šámal, R.
Rok
2020
Publikováno
Electronic Journal of Combinatorics (E-JC),. 2020, 27(2), ISSN 1077-8926.