Counting Circuit Double Covers
Autor: | Hušek, Radek, Šámal, Robert |
---|---|
Rok vydání: | 2023 |
Předmět: | |
Druh dokumentu: | Working Paper |
Popis: | 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. Comment: Proofs and figures improved. Replaced term "gadget" with "multipole" (as defined by Nedela and \v{S}koviera) |
Databáze: | arXiv |
Externí odkaz: |