Cycle double covers and the semi-Kotzig frame

Let H be a cubic graph admitting a 3-edge-coloring c:E(H)→Z₃ such that the edges colored with 0 and μ∈{1,2} induce a Hamilton circuit of H and the edges colored with 1 and 2 induce a 2-factor F. The graph H is semi-Kotzig if switching colors of edges in any even subgraph of F yields a new 3-edge-coloring of H having the same property as c. A spanning subgraph H of a cubic graph G is called a semi-Kotzig frame if the contracted graph G/H is even and every non-circuit component of H is a subdivision of a semi-Kotzig graph.In this paper, we show that a cubic graph G has a circuit double cover if it has a semi-Kotzig frame with at most one non-circuit component. Our result generalizes some results of Goddyn [L.A. Goddyn, Cycle covers of graphs, Ph.D. Thesis, University of Waterloo, 1988], and Häggkvist and Markström [R. Häggkvist, K. Markström, Cycle double covers and spanning minors I, J. Combin. Theory Ser. B 96 (2006) 183-206].     

Cycle double covers and spanning minors II

In this paper we continue our investigations from [R. Häggkvist, K. Markström, Cycle double covers and spanning minors, Technical Report 07, Department of Mathematics, Umeå University, Sweden, 2001, J. Combin. Theory, Ser. B, to appear] regarding spanning subgraphs which imply the existence of cycle double covers. We prove that if a cubic graph G has a spanning subgraph isomorphic to a subdivision of a bridgeless cubic graph on at most 10 vertices then G has a CDC. A notable result is thus that a cubic graph with a spanning Petersen minor has a CDC, a result also obtained by Goddyn [L. Goddyn, Cycle covers of graphs, Ph.D. Thesis, University of Waterloo, 1988].     

Contractible edges in non-separating cycles

An edge of ak-connected graph is said to bek-contractible if the contraction of the edge results in ak-connected graph. We prove that every triangle-freek-connected graphG has an induced cycleC such that all edges ofC arek-contractible and such thatG–V(C) is (k–3)-connected (k4). This result unifies two theorems by Thomassen [5] and Egawa et. al. [3].Dedicated to Professor Toshiro Tsuzuku on his sixtieth birthday     

Orthogonal double covers by super‐extendable cycles

An Orthogonal Double Cover (ODC) of the complete graph K_n by an almost‐hamiltonian cycle is a decomposition of 2K_n into cycles of length n?1 such that the intersection of any two of them is exactly one edge. We introduce a new class of such decompositions. If n is a prime, the special structure of such a decomposition allows to expand it to an ODC of K_n+1 by an almost‐hamiltonian cycle. This yields the existence of an ODC of K_p+1 by an almost‐hamiltonian cycle for primes p of order 3 mod 4 and its eventual existence for arbitrary primes p. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 283–293, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10011     

Note on non-separating and removable cycles in highly connected graphs

We combine two well-known results by Mader and Thomassen, respectively. Namely, we prove that for any k-connected graph G (k≥4), there is an induced cycle C such that G−V(C) is (k−3)-connected and G−E(C) is (k−2)-connected. Both “(k−3)-connected” and “(k−2)-connected” are best possible in a sense.     

Flows, flow-pair covers and cycle double covers

In this paper, some earlier results by Fleischner [H. Fleischner, Bipartizing matchings and Sabidussi’s compatibility conjecture, Discrete Math. 244 (2002) 77-82] about edge-disjoint bipartizing matchings of a cubic graph with a dominating circuit are generalized for graphs without the assumption of the existence of a dominating circuit and 3-regularity. A pair of integer flows (D,f₁) and (D,f₂) is an (h,k)-flow parity-pair-cover of G if the union of their supports covers the entire graph; f₁ is an h-flow and f₂ is a k-flow, and . Then G admits a nowhere-zero 6-flow if and only if G admits a (4,3)-flow parity-pair-cover; and G admits a nowhere-zero 5-flow if G admits a (3,3)-flow parity-pair-cover. A pair of integer flows (D,f₁) and (D,f₂) is an (h,k)-flow even-disjoint-pair-cover of G if the union of their supports covers the entire graph, f₁ is an h-flow and f₂ is a k-flow, and for each {i,j}={1,2}. Then G has a 5-cycle double cover if G admits a (4,4)-flow even-disjoint-pair-cover; and G admits a (3,3)-flow parity-pair-cover if G has an orientable 5-cycle double cover.     

Small cycle double covers of products I: Lexicographic product with paths and cycles

Bondy conjectured that every simple bridgeless graph has a small cycle double cover (SCDC). We show that this is the case for the lexicographic products of certain graphs and along the way for the Cartesian product as well. Specifically, if G does not have an isolated vertex then G □ P₂ and G □ C_2k have SCDCs. If G has an SCDC then so does G □ P_k, k > 2 and G □ C_{2k + 1}. We use these Cartesian results to show that P_2j[G] (j ≥ 1) and C_k[G] (k ≠ 3, 5, 7) have SCDCs. Also, if G has an SCDC then so does P_{2j + 1}[G] (j ≥ 4). The results for the lexicographic product are harder and, in addition to the Cartesian results, require certain decompositions of K_n,n into perfect matchings. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 99–123, 2008     

Counting double covers of graphs

Any group of automorphisms of a graph G induces a notion of isomorphism between double covers of G. The corresponding isomorphism classes will be counted.     

Graphs with Cayley canonical double covers

A canonical double cover $B\left(X\right)$ of a graph $X$ is the direct product of $X$ and the complete graph $K_2$ on two vertices. In order to answer the question when a canonical double cover of a given graph is a Cayley graph, in 1992 Maru?i? et al. introduced the concept of generalized Cayley graphs. In this paper this concept is generalized to a wider class of graphs, the so-called extended generalized Cayley graphs. It is proved that the canonical double cover of a connected non-bipartite graph $X$ is a Cayley graph if and only if $X$ is an extended generalized Cayley graph. This corrects an incorrectly stated claim in [Discrete Math. 102 (1992), 279–285].     

Orthogonal double covers of Cayley graphs

Let X and G be graphs, such that G is isomorphic to a subgraph of X.An orthogonal double cover (ODC) of X by G is a collection of subgraphs of X, all isomorphic with G, such that (i) every edge of X occurs in exactly two members of and (ii) and share an edge if and only if x and y are adjacent in X. The main question is: given the pair (X,G), is there an ODC of X by G? An obvious necessary condition is that X is regular.A technique to construct ODCs for Cayley graphs is introduced. It is shown that for all (X,G) where X is a 3-regular Cayley graph on an abelian group there is an ODC, a few well known exceptions apart.     

On orthogonal double covers by trees

A collection 𝒫 of n spanning subgraphs of the complete graph K_n is said to be an orthogonal double cover (ODC) if every edge of K_n belongs to exactly two members of 𝒫 and every two elements of 𝒫 share exactly one edge. We consider the case when all graphs in 𝒫 are isomorphic to some tree G and improve former results on the existence of ODCs, especially for trees G of short diameter and for trees of G on few vertices. © 1997 John Wiley & Sons, Inc. J Combin Designs 5:433–441, 1997     

Perfect path double covers of graphs

A perfect path double cover (PPDC) of a graph G on n vertices is a family ?? of n paths of G such that each edge of G belongs to exactly two members of ?? and each vertex of G occurs exactly twice as an end of a path of ??. We propose and study the conjecture that every simple graph admits a PPDC. Among other things, we prove that every simple 3-regular graph admits a PPDC consisting of paths of length three.     

Optimal covers with Hamilton cycles in random graphs

A packing of a graph G with Hamilton cycles is a set of edge-disjoint Hamilton cycles in G. Such packings have been studied intensively and recent results imply that a largest packing of Hamilton cycles in G _n,p a.a.s. has size ?δ(G _n,p )/2?. Glebov, Krivelevich and Szabó recently initiated research on the ‘dual’ problem, where one asks for a set of Hamilton cycles covering all edges of G. Our main result states that for \(\tfrac{{log^{117} n}} {n} \leqslant p \leqslant 1 - n^{ - 1/8}\) , a.a.s. the edges of G _n,p can be covered by ?Δ (G _n,p )/2? Hamilton cycles. This is clearly optimal and improves an approximate result of Glebov, Krivelevich and Szabó, which holds for p ≥ n ^?1+?. Our proof is based on a result of Knox, Kühn and Osthus on packing Hamilton cycles in pseudorandom graphs.     

Note on cycle double covers of graphs

Kriesell [M. Kriesell, Contractions, cycle double covers and cyclic colorings in locally connected graphs, J. Combin. Theory Ser. B 96 (2006) 881-900] proved the cycle double cover conjecture for locally connected graphs. In this note, we give much shorter proofs for two stronger results.     

The brauer group and ramified double covers of surfaces

Let Z be a nonsingular plane curve of even degree and U = P ² — Z. Let : X —> P ² be tbe double cover ramified over Z and V = ^—1(U). It is shown that the kernel of the restriction map on Brauer groups^" : B(U) —> B(V), is isomorphic to Z/2(²) where ρ— 2 < r <ρ— 1, p being the Picard number of X and if ^" : Pic P² —> Pic X is an isomorphism, exactly half of the algebra classes of order 2 in B(X) are restrictions of algebra classes of order 2 in B(U) whose ramification has been split by V. The kernel of the corestriction map 2 B(V) — ₂B(U) is shown to be the subgroup consisting of elements fixed by the Galois group.     

Perfect double covers with paths of length four

It is shown that for any 4-regular graph G there is a collection F of paths of length 4 such that each edge of G belongs to exactly two of the paths and each vertex of G occurs exactly twice as an endvertex of a path of F. This proves a special case of a conjecture of Bondy. © 1996 John Wiley & Sons, Inc.     

Cycle covers of graphs with a nowhere-zero 4-flow

It is shown that the edges of a simple graph with a nowhere-zero 4-flow can be covered with cycles such that the sum of the lengths of the cycles is at most |E(G)| + |V(G)| ?3. This solves a conjecture proposed by G. Fan.