Shortest Circuit Covers and Postman Tours in Graphs with a Nowhere Zero 4
Bill Jackson · SIAM Journal on Computing · 1990
Let G be a graph with a nowhere zero 4-flow. It is shown that the length of a shortest circuit cover of $E(G)$ is equal to the length of a shortest postman tour of $E(G)$. Using this result an efficient algorithm for constructing shortest circuit covers for graphs that possess two disjoint spanning trees is obtained. It is also deduced that if H is a $2m$-edge connected graph, $m \geqq 2$, then there exists a circuit cover of $E(H)$ of length at most $|E(H)|+\min \{ {{| E(H) |} / {(2m + 1)}}, | V(H) | - 1 \}$ and that if G has a nowhere zero 4-flow, then there exists a circuit cover of $V(G)$ of length at most $2|V(G)| -2$. Finally, it is shown that the equivalence between shortest circuit covers and postman tours may be extended to binary matroids that possess a nowhere zero $\mathbb{Z} _2 ^2$-flow.