Short cycle covers of graphs and nowhere-zero flows
Edita Máčajová, André Raspaud, Michael Tarsi, Xuding Zhu · Journal of Graph Theory · 2011
A shortest cycle cover of a graph G is a family of cycles which together cover all the edges of G and the sum of their lengths is minimum. In this article we present upper bounds to the length of shortest cycle covers, associated with the existence of two types of nowhere-zero flows—circular flows and Fano flows. Fano flows, or Fano colorings, are nowhere-zero ℤ-flows on cubic graphs, with certain restrictions on the flow values meeting at a vertex. Such flows are conjectured to exist on every bridgless cubic graph. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 68:340-348, 2011