Counting Circuit Double Covers

2023/03/19 by Radek Hušek, Robert Šámal, Hušek, Radek +1 · 1 citation
Computer Science · Mathematics · #05C38 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2303.10615

openalex publication_date 2023/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Counting Small Cycle Double Covers

Related

• Exponentially Many Circuit Double Covers
• Cycle Double Cover Conjecture
• Counting Small Cycle Double Covers
• A proof of the Cycle Double Cover Conjecture
• Approximate cycle double cover