2025/06/12 by Jooken, Jorik, Seamone, Ben, Zamfirescu, Carol T.
#05C10 #05C30 #05C38 #05C45 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2506.10604
A theorem due to Seyffarth states that every planar 4-connected n-vertex graph has a cycle double cover (CDC) containing at most n-1 cycles (a "small" CDC). We extend this theorem by proving that, in fact, such a graph must contain linearly many small CDCs (in terms of n), and provide stronger results in the case of planar 4-connected triangulations. We complement this result with constructions of planar 4-connected graphs which contain at most polynomially many small CDCs. Thereafter we treat cubic graphs, strengthening a lemma of Hušek and Šámal on the enumeration of CDCs, and, motivated by a conjecture of Bondy, give an alternative proof of the result that every planar 2-connected cubic graph on n > 4 vertices has a CDC of size at most n/2. Our proof is much shorter and obtained by combining a decomposition based argument, which might be of independent interest, with further combinatorial insights. Some of our results are accompanied by a version thereof for CDCs containing no cycle twice.