Attempts to prove the CDC conjecture have led to various conjectured strengthenings, such as the faithful circuit cover problem (Problem 2.1.4), strong circuit double cover problem (Conjecture 1.5.1), even covering problems (Conjectures 2.4.1 and 2.4.2), 5-even subgraph double cover problem (Conjecture 4.1.4), etc. Verification of any of those stronger problems will imply the CDC conjecture.

In this chapter, we present another type of variation of the double cover problem: directed circuit double covering. These are, in general, much stronger than the CDC problem. And some of them have already been completely characterized.

Historically, the paper by Tutte [229] on orientable circuit double cover is the earliest published article related to the CDC problem.

Orientable double cover

Definition 13.1.1 Let G = (V, E) be a graph and D be an orientation of E(G). A directed even subgraph H of the directed graph D(G) is a subgraph of D(G) such that for each vertex v of H, the indegree of v equals the outdegree of v.

Definition 13.1.2 (1) Let ℱ = {C1, …, Cr} be an even subgraph double cover of a graph G. The set ℱ is an orientable even subgraph double cover if there is an orientation Dµ on E(Cµ), for each µ = 1, …, r, such that

(i) Dµ(Cµ) is a directed even subgraph, and

(ii) for each edge e contained in two even subgraphs Cα and Cβ (α, β ∈ {1, …, r}), the directions of Dα(Cα) and Dβ(Cβ) are opposite on e.