1‐Factor and Cycle Covers of Cubic Graphs |
| |
Authors: | Eckhard Steffen |
| |
Institution: | PADERBORN INSTITUTE FOR ADVANCED STUDIES IN COMPUTER SCIENCE AND ENGINEERING, PADERBORN UNIVERSITY, PADERBORN, GERMANY |
| |
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 18 . We also give a negative answer to a problem stated in 18 . |
| |
Keywords: | cycle covers cubic graphs 1‐factors Berge‐Fulkerson conjecture conjecture of Fan and Raspaud 5‐cycle double cover conjecture |
|
|