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 and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.