1-factor and cycle covers of cubic graphs

Abstract

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)\ne 0$, 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. We also give a negative answer to a problem of Zhang.

final version

References in corpus (2)

• Generation and Properties of Snarks
• On the perfect matching index of bridgeless cubic graphs

Cited by in corpus (11)

• Petersen cores and the oddness of cubic graphs
• An equivalent formulation of the Fan-Raspaud Conjecture and related problems
• Some snarks are worse than others
• On measures of edge-uncolorability of cubic graphs: A brief survey and some new results
• Ban--Linial's Conjecture and treelike snarks
• Shortest cycle covers and cycle double covers with large 2-regular subgraphs
• Unions of 1-factors in $r$-graphs and overfull graphs
• On the maximum fraction of edges covered by t perfect matchings in a cubic bridgeless graph
• Partially normal 5-edge-colorings of cubic graphs
• Covering a cubic graph by 5 perfect matchings
• Cores, joins and the Fano-flow conjectures