zbMATH — the first resource for mathematics

1-factor and cycle covers of cubic graphs. (English) Zbl 1309.05108
Summary: Let \(G\) be a bridgeless cubic graph. Consider a list of \(k\) 1-factors of \(G\). Let \(E_i\) be the set of edges contained in precisely \(i\) members of the \(k\) 1-factors. Let \(\mu_k(G)\) be the smallest \(|E_0|\) over all lists of \(k\) 1-factors of \(G\). Any list of three 1-factors induces a core of a cubic graph. We use results on the structure of cores to prove sufficient conditions for Berge-covers and for the existence of three 1-factors with empty intersection.
Furthermore, if \(\mu_3(G)\neq0\), then \(2\mu_3(G)\) is an upper bound for the girth of \(G\). We also prove some new upper bounds for the length of shortest cycle covers of bridgeless cubic graphs. Cubic graphs with \(\mu_4(G)=0\) have a 4-cycle cover of length \(\frac{4}{3}|E(G)|\) and a 5-cycle double cover. These graphs also satisfy two conjectures of Zhang [C.-Q. Zhang, Integer flows and cycle covers of graphs. New York, NY: Marcel Dekker (1996; Zbl 0866.05001)]. We also give a negative answer to a problem stated in [loc. cit.].

05C38 Paths and cycles
Full Text: DOI arXiv
[1] Alon, Covering multigraphs by simple circuits, SIAM J Algebraic Discrete Methods 6 pp 345– (1985) · Zbl 0581.05046 · doi:10.1137/0606035
[2] Bermond, Shortest coverings 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] Brinkmann, Generation and properties of snarks, J Combin Theory Ser B 103 pp 468– (2013) · Zbl 1301.05119 · doi:10.1016/j.jctb.2013.05.001
[4] Fan, Fulkerson’s conjecture and circuit covers, J Combin Theory Ser B 61 pp 133– (1994) · Zbl 0811.05053 · doi:10.1006/jctb.1994.1039
[5] J. L. Fouquet J. M. Vanherpe On the perfect matching index of bridgeless cubic graphs
[6] Fulkerson, Blocking and antiblocking pairs of polyhedra, Math Program 1 pp 168– (1971) · Zbl 0254.90054 · doi:10.1007/BF01584085
[7] Häggkvist, Problem 443. Special case of the Fulkerson Conjecture, Discrete Math 307 pp 650– (2007)
[8] X. Hou H.-J. Lai C.-Q. Zhang On matching coverings and cycle coverings
[9] Jaeger, Conjecture 1 and 2, In: Combinatorics 79’ (M. Deza, I. G. Rosenberg, Eds.), Ann Disc Math 9 pp 305– (1980)
[10] Kochol, Snarks without small cycles, J Combin Theory Ser B 67 pp 34– (1996) · Zbl 0855.05066 · doi:10.1006/jctb.1996.0032
[11] Máčajová, Short cycle covers of graphs and nowhere-zero flows, J Graph Theory 68 pp 340– (2011) · Zbl 1234.05138 · doi:10.1002/jgt.20563
[12] Máčajová, Technical reports in Informatics TR-2009-020, Faculty of Mathematics, Physics, and Informatics (2009)
[13] Máčajová, Constructing hypohamiltonian snarks with cyclic connectivity 5 and 6, Electronic J Combin 14 (2007)
[14] Mazzuoccolo, The equivalence of two conjectures of Berge and Fulkerson, J Graph Theory 68 pp 125– (2011) · Zbl 1230.05238 · doi:10.1002/jgt.20545
[15] Petersen, Die Theorie der regulären graphs, Acta Mathematica 15 pp 193– (1891) · JFM 23.0115.03 · doi:10.1007/BF02392606
[16] Seymour, On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc London Math Soc 38 (3) pp 423– (1979) · Zbl 0411.05037 · doi:10.1112/plms/s3-38.3.423
[17] Steffen, Classifications and characterizations of snarks, Discrete Math 188 pp 183– (1998) · Zbl 0956.05089 · doi:10.1016/S0012-365X(97)00255-0
[18] Zhang, Integer flows and cycle covers of graphs (1997)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.