Flows, flow-pair covers and cycle double covers (Q1044934)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Flows, flow-pair covers and cycle double covers |
scientific article |
Statements
Flows, flow-pair covers and cycle double covers (English)
0 references
15 December 2009
0 references
In this paper, some earlier results by \textit{H. Fleischner} [``Bipartizing matchings and Sabidussi's compatibility conjecture'', Discrete Math. 244, No. 1--3, 77--82 (2002; Zbl 0989.05063)] 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_{1})\) and \((D,f_{2})\) is an \((h,k)\)-flow parity-pair-cover of \(G\) if the union of their supports covers the entire graph; \(f_{1}\) is an \(h\)-flow and \(f_{2}\) is a \(k\)-flow, and \(E_{f_1=\mathrm{odd}}=E_{f_2=\mathrm{odd}}\). 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_{1})\) and \((D,f_{2})\) is an \((h,k)\)-flow even-disjoint-pair-cover of \(G\) if the union of their supports covers the entire graph, \(f_{1}\) is an \(h\)-flow and \(f_{2}\) is a \(k\)-flow, and \(E_{f_i=\mathrm{even},f_i\neq 0}\subseteq E_{f_j=0}\) 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.
0 references
integer flow
0 references
flow cover
0 references
cycle double cover
0 references