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: |
|