Counting Circuit Double Covers

03/19/2023

∙

by   Radek Hušek, et al.

∙

0

∙

share

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.