Journal of Graph Theory · 2014 · 42 citations · 13 references
Natural SciencesComputer ScienceMathematicsCombinatoricsTheory Of ComputationTopologyDirected Acyclic GraphsEnumerative CombinatoricsGeometric GraphsGraph AlgorithmsGraph TheoryTopological CombinatoricsComputational Complexity Of Graph AlgorithmsIntersectionUpper Bound ComputationUpper Bounds
Abstract Let G be a bridgeless cubic graph. Consider a list of k 1‐factors of G . Let be the set of edges contained in precisely i members of the k 1‐factors. Let be the smallest 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 , then 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 have a 4‐cycle cover of length and a 5‐cycle double cover. These graphs also satisfy two conjectures of Zhang . We also give a negative answer to a problem stated in .
13
Blocking and anti-blocking pairs of polyhedra
D. R. Fulkerson · Mathematical Programming · 1971 · 540 citations
Generation and properties of snarks
Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund et al. · 2016 · 105 citations
Martin Kochol · Journal of Combinatorial Theory Series B · 1996 · 103 citations