1‐Factor and Cycle Covers of Cubic Graphs

Eckhard Steffen

Journal of Graph Theory · 2014 · 42 citations · 13 references

DOIFull text

Open access

Concepts

Abstract

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 .

References

13