Premium
Short cycle covers of graphs and nowhere‐zero flows
Author(s) -
Máčajová Edita,
Raspaud André,
Tarsi Michael,
Zhu Xuding
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20563
Subject(s) - mathematics , combinatorics , fano plane , vertex (graph theory) , graph , cubic graph , zero (linguistics) , flow (mathematics) , upper and lower bounds , theory of computation , discrete mathematics , line graph , geometry , voltage graph , mathematical analysis , algorithm , linguistics , philosophy
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 ℤ 3 2 ‐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