×

Short cycle covers of graphs and nowhere-zero flows. (English) Zbl 1234.05138

Summary: 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 \(\mathbb Z^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 bridgeless cubic graph.

MSC:

05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C21 Flows in graphs
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, Covering multigraphs by simple circuits, SIAM J Algebraic Discrete Meth 6 pp 345– (1985) · Zbl 0581.05046 · doi:10.1137/0606035
[2] Bermond, Shortest covering of graphs with cycles, J Combin Theory Ser B 35 pp 297– (1983) · Zbl 0559.05037 · doi:10.1016/0095-8956(83)90056-4
[3] U. A. Celmins On cubic graphs that do no have an edge 3-coloring 1984
[4] Fan, Tutte’s 3-flow conjecture and short cycle cover, J Combin Theory Ser B 57 pp 36– (1993) · Zbl 0723.05078 · doi:10.1006/jctb.1993.1004
[5] Fan, Fulkerson’s conjecture and circuit covers, J Combin Theory Ser B 16 pp 133– (1994) · Zbl 0811.05053 · doi:10.1006/jctb.1994.1039
[6] Fleischner, Eine gemeinsame basis für die theorie der eulerschen graphen und den satz von petersen, Monatsh Math 81 pp 267– (1976) · Zbl 0347.05109 · doi:10.1007/BF01387754
[7] Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math Prog 1 pp 168– (1971) · Zbl 0254.90054 · doi:10.1007/BF01584085
[8] Goddyn, On (k, d)-colourings and fractional nowhere-zero flows, J Graph Theory 28 pp 155– (1998) · Zbl 0922.05027 · doi:10.1002/(SICI)1097-0118(199807)28:3<155::AID-JGT5>3.0.CO;2-J
[9] Jaeger, Selected Topics in Graph Theory 3 pp 71– (1988)
[10] F. Jaeger private comunication 1985
[11] Jamshi, Short circuit covers for regular matroids with a nowhere-zero 5-flow, J Combin Theory Ser B 42 pp 384– (1987)
[12] Kaiser, Short cycle covers of graphs with minimum degree three, SIAM J Discrete Math 24 pp 330– (2010) · Zbl 1216.05048 · doi:10.1137/080717468
[13] Král’, Projective, affine, and abelian colourings of cubic graphs, European J Combin 30 pp 53– (2009) · Zbl 1198.05019 · doi:10.1016/j.ejc.2007.11.029
[14] Máčajová, Fano colourings of cubic graphs and the fulkerson conjecture, Theoret Comput Sci 349 pp 112– (2005) · Zbl 1082.05040 · doi:10.1016/j.tcs.2005.09.034
[15] M. Preissmann Sur les colorations des arêtes des graphs cubiques eme 1981
[16] A. Raspaud Short cycle covers for binary matroids with a Petersen Flow 1992
[17] A. Raspaud Flots et couvertures par des cycles dans les graphes et les matroïdes ème 1985
[18] Seymour, Nowhere-zero 6-flows, J Combin Theory Ser B 30 pp 130– (1981) · Zbl 0474.05028 · doi:10.1016/0095-8956(81)90058-7
[19] Shu, A note about shortest cycle covers, Discrete Math 301 pp 232– (2005) · Zbl 1097.05023 · doi:10.1016/j.disc.2005.06.013
[20] C. Thomassen On the complexity of minimum cycle covers of graphs 1994
[21] Zhang, Integer Flows and Cycle Covers of Graphs (1997)
[22] Zhu, Circular chromatic number, a survey, Discrete Math 229 pp 371– (2001) · Zbl 0973.05030 · doi:10.1016/S0012-365X(00)00217-X
[23] Zhu, Algorithms and Combinatorics, in: Topics in Discrete Mathematics pp 497– (2006) · doi:10.1007/3-540-33700-8_25
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.