Integer flows and cycle covers

Here the graphs may contain loops and multiple edges. A cover of \(G\) is a collection \({\mathcal H}\) of subgraph of \(G\) which covers all edges of \(G\); \({\mathcal H}\) is called an \(m\)-cover if each edge of \(G\) is covered exactly \(m\) times. \textit{D. R. Fulkerson} [Math. Programming 1, 168-194 (1971; Zbl 0254.90054)] had posed a conjecture equivalent to: Every bridgeless graph has a 4-cover by 6 even subgraphs. On the other hand, it follows from a result of \textit{P. D. Seymour} [Proc. Lond. Math. Soc., III. Ser. 38, 423-460 (1979; Zbl 0411.05037)] that the Petersen graph has no 6- cover by 9 even subgraphs. The author shows that every bridgeless graph has a 6-cover by 10 even subgraphs whence follows the theorem that every bridgeless graph has a cycle \(m\)-cover for any even \(m\geq 4\). Suppose \(G\) has two disjoint spanning trees. \textit{A. Itai} and \textit{M. Rodeh} [Automata, Languages and Programming; 5th Colloq., Udine 1978, Lect. Notes Comput. Sci. 62, 289-299 (1978; Zbl 0386.05047)] proved that \(G\) can be covered by two even subgraphs with total size at most \(| E(G)|+| V(G)|-1\) while \textit{F. Jaeger} [J. Combin. Theory, Ser. B 26, 205-216 (1979; Zbl 0422.05028)] showed \(G\) must have a nowhere-zero 4-flow. The author shows that if \(G\) has a nowhere-zero 4- flow, then the minimum total size of two even subgraphs which together cover \(G\) is at most \(| E(G)|+| V(G)|-1\), with equality iff \(G\) is an odd multi-tree plus some loops or \(| V(G)|=1\).

Recommendations

Cites work

Cited in

(23)

This page was built for publication: Integer flows and cycle covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1186130)