Petersen Cores and the Oddness of Cubic Graphs
Petersen Cores and the Oddness of Cubic Graphs
复制标题
DOI：
10.1002/jgt.22014
复制
发表时间：
2015-01
影响因子：
0.9
通讯作者：
Li-gang Jin;E. Steffen
中科院分区：
文献类型：
--
作者：
Li-gang Jin;E. Steffen
设G是无桥三次图。考虑G的k 1-因子列表。设Ei是包含在k个1-因子的i个成员中的边的集合。设μk（G）是最小的|E0|在G的所有k 1-因子列表上我们通过三个1因子来研究列表，并调用G[E0 <$E2 <$E3]，|E0| =μ3（G）a μ3（G）-G的核心。如果G不是3边可着色的，则μ3（G）≥3。在Steffen（J Graph Theory 78（2015），195-206）中，证明了如果μ3（G）≥ 0，则2μ3（G）是G围长的上界。我们证明了μ3（G）也是G的奇性ω（G）的界.证明了ω（G）≤23μ3（G）.如果ω（G）=23μ3（G），那么每个μ3（G）-核都有一个非常特殊的结构。我们称这些核为彼得森核。我们证明了对于任意给定的奇性，存在一个循环4边连通三次图G，使得ω（G）=23μ3（G）.另一方面，ω（G）和23μ3（G）之间的差可以是任意大的。即使我们另外修正了奇数，这也是正确的。此外，对任意整数k≥3，存在无桥三次图G，使得μ3（G）=k .
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. We study lists by three 1‐factors, and call G[E0∪E2∪E3] with |E0|=μ3(G) a μ3(G) ‐core of G. If G is not 3‐edge‐colorable, then μ3(G)≥3 . In Steffen (J Graph Theory 78 (2015), 195–206) it is shown that if μ3(G)≠0 , then 2μ3(G) is an upper bound for the girth of G. We show that μ3(G) bounds the oddness ω(G) of G as well. We prove that ω(G)≤23μ3(G) . If ω(G)=23μ3(G) , then every μ3(G) ‐core has a very specific structure. We call these cores Petersen cores. We show that for any given oddness there is a cyclically 4‐edge‐connected cubic graph G with ω(G)=23μ3(G) . On the other hand, the difference between ω(G) and 23μ3(G) can be arbitrarily big. This is true even if we additionally fix the oddness. Furthermore, for every integer k≥3 , there exists a bridgeless cubic graph G such that μ3(G)=k .