For a set C of directed circuits of a graph G that form an oriented circuit double cover, we denote by IC the graph with vertex set C, in which two circuits C and C′ are connected by k edges if |C ∩ C′| = k. Let Φ∗ c (G) = minχc(IC), where the minimum is taken over all the oriented circuit double covers of G. It is easy to show that for any graph G, Φc(G) ≤ Φ∗c (G). On the other hand, it follows from well-known results that for any integer 2 ≤ k ≤ 4, Φ∗c (G) ≤ k if and only if Φc(G) ≤ k; for any integer k ≥ 1, Φ∗c (G) ≤ 2 + 1 k if and only if Φc(G) ≤ 2 + 1 k. This papers proves that for any rational number 2 ≤ r ≤ 5 there exists a graph G for which Φ∗c (G) = Φc(G) = r. We also show that there are graphs G for which Φc(G) < Φ∗c (G).
Relation:
Bulletin of the Institute of Mathematics Academia Sinica New Series 5(4), pp.349-368
