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
    0 references
    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

    Identifiers