共查询到3条相似文献,搜索用时 0 毫秒
1.
G. Mazzuoccolo 《Journal of Graph Theory》2011,68(2):125-128
Let G be a bridgeless cubic graph. Fulkerson conjectured that there exist six 1‐factors of G such that each edge of G is contained in exactly two of them. Berge conjectured that the edge‐set of G can be covered with at most five 1‐factors. We prove that the two conjectures are equivalent. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:125‐128, 2011 相似文献
2.
Giuseppe Mazzuoccolo 《Journal of Graph Theory》2013,73(4):377-376
We construct a family of r‐graphs having a minimum 1‐factor cover of cardinality (disproving a conjecture of Bonisoli and Cariolaro, Birkhäuser, Basel, 2007, 73–84). Furthermore, we show the equivalence between the statement that is the best possible upper bound for the cardinality of a minimum 1‐factor cover of an r‐graph and the well‐known generalized Berge–Fulkerson conjecture. 相似文献
3.
Eckhard Steffen 《Journal of Graph Theory》2015,78(3):195-206
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 . 相似文献