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.     

Shorter signed circuit covers of graphs

A signed circuit is a minimal signed graph (with respect to inclusion) that admits a nowhere-zero flow. We show that each flow-admissible signed graph on edges can be covered by signed circuits of total length at most , improving a recent result of Cheng et al. To obtain this improvement, we prove several results on signed circuit covers of trees of Eulerian graphs, which are connected signed graphs such that removing all bridges results in a collection of Eulerian graphs.     

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.     

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

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.     

Score vectors of Kotzig tournaments

An n-tournament T_n is said to be a Kotzig tournament if the n subtournaments of T_n of order n − 1 are isomorphic. And a nonnegative integral vector R is said to be potentially Kotzig if there exists some Kotzig tournament T_n such that its score vector is R. In this paper, a criterion is found for determining whether a non-negative integral vector R is potentially Kotzig.     

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.     

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.     

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