This is a reference request question. Let $G$ be an arbitrary cubic graph.
Is the problem of finding a cycle double cover $D$ of $G$ with minimum number of cycles in $D$ studied in the literature?

I couldn't find anything related to this in the literature, except for cycle double covers $D$ comprised of (exactly) three cycles. It is known that cycle double covers comprised of three cycles (3-CDC) have many interesting properties, e.g.: all three cycles in a 3-CDC are Hamiltonian cycles, and hence the cover will be a Hamiltonian double cover (also called a perfect 1-factorization). If $G$ admits such a cover, then $G$ is said to be perfectly 1-factorable (another name is Kotzig graph, in honor of Kotzig who presumably studied them for the first time).

I am particularly interested in cycle double covers of $G$ comprised of exactly four cycles (of equal length, preferably).

Note: I thought a cubic graph $G$ has a 3-CDC iff $G$ has a nowhere-zero 4-flow due to Jaeger's characterization [4], but that wouldn't work because a "cycle" in [4] basically means "an even (sub)graph" (i.e. a graph where all vertices have even degree). It is true that a cubic graph has a double cover comprised of three even graphs iff $G$ has nowhere-zero 4-flow. But, this is different from cycle double covers comprised of exactly three cycles.


[1] Zhang, Circuit Double Cover of Graphs (Book), Cambridge University Press (2012)

[2] Rosa, Alexander, Perfect 1-factorizations, ZBL07093124.

[3] Fetter, Hans L., Some basic properties of multiple Hamiltonian covers, Discrete Appl. Math. 154, No. 13, 1803-1815 (2006). ZBL1096.05032.

[4] Jaeger, François, A survey of the cycle double cover conjecture, Cycles in graphs, Workshop Simon Fraser Univ., Burnaby/Can. 1982, Ann. Discrete Math. 27, 1-12 (1985). ZBL0585.05012.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.