1‐Factor and Cycle Covers of Cubic Graphs
1‐Factor and Cycle Covers of Cubic Graphs
复制标题
DOI：
10.1002/jgt.21798
复制
发表时间：
2012-09
影响因子：
0.9
通讯作者：
E. Steffen
中科院分区：
文献类型：
--
作者：
E. Steffen
设G是无桥三次图。考虑G的k 1-因子列表。设Ei是包含在k个1-因子的i个成员中的边的集合。设μk（G）是最小的|E0|在G的所有k 1-因子列表上任何三个1因子的列表都导出一个三次图的核。我们使用核结构的结果来证明Berge覆盖和存在三个空交的1因子的充分条件。进一步地，如果μ3（G）≥ 0，则2μ3（G）是G围长的上界.我们还证明了无桥三次图的最短圈覆盖长度的一些新的上界。μ4（G）=0的三次图的4圈覆盖长度为43| E（G）|和5个循环的双重覆盖这些图也满足张的两个定理。我们也给一个否定的答案中所述的问题。
Let G be a bridgeless cubic graph. Consider a list of k 1‐factors of G. Let Ei be the set of edges contained in precisely i members of the k 1‐factors. Let μk(G) be the smallest |E0| 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 μ3(G)≠0 , then 2μ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 μ4(G)=0 have a 4‐cycle cover of length 43|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 stated in .