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].     

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.     

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.     

Torsion-free covers II

This paper continues the study of the existence of torsion-free covers with respect to a faithful hereditary torsion theory (ℑ,F) of left modules over a ringR with unity. If the filter of left ideals associated with (ℑ,F) has a cofinal subset of finitely generated left ideals, then every leftR-module has a torsion-free cover. An example is given to illustrate how this result generalizes all previously known existence theorems for torsion-free covers.     

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.     

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.     

Circuit double covers in special types of cubic graphs

Suppose that a 2-connected cubic graph G of order n has a circuit C of length at least n−4 such that G−V(C) is connected. We show that G has a circuit double cover containing a prescribed set of circuits which satisfy certain conditions. It follows that hypohamiltonian cubic graphs (i.e., non-hamiltonian cubic graphs G such that G−v is hamiltonian for every v∈V(G)) have strong circuit double covers.     

Cyclic orthogonal double covers of 4-regular circulant graphs

An orthogonal double cover (ODC) of a graph H is a collection G={G_v:v∈V(H)} of |V(H)| subgraphs of H such that every edge of H is contained in exactly two members of G and for any two members G_u and G_v in G, |E(G_u)∩E(G_v)| is 1 if u and v are adjacent in H and it is 0 if u and v are nonadjacent in H. An ODC G of H is cyclic (CODC) if the cyclic group of order |V(H)| is a subgroup of the automorphism group of G. In this paper, we are concerned with CODCs of 4-regular circulant graphs.     

Small cycle double covers of 4-connected planar graphs

Acycle double cover of a graph,G, is a collection of cycles,C, such that every edge ofG lies in precisely two cycles ofC. TheSmall Cycle Double Cover Conjecture, proposed by J. A. Bondy, asserts that every simple bridgeless graph onn vertices has a cycle double cover with at mostn–1 cycles, and is a strengthening of the well-knownCycle Double Cover Conjecture. In this paper, we prove Bondy's conjecture for 4-connected planar graphs.