On $2$-Factors in $r$-Connected $\{K_{1,k},P_4\}$-Free Graphs
On $2$-Factors in $r$-Connected $\{K_{1,k},P_4\}$-Free Graphs
复制标题
DOI：
10.3836/tjm/1233844061
复制
发表时间：
2008
影响因子：
0.6
通讯作者：
Y. Egawa;J. Fujisawa;S. Fujita;K. Ota
中科院分区：
文献类型：
--
作者：
Y. Egawa;J. Fujisawa;S. Fujita;K. Ota
.在[3]中，Faudree等人考虑了命题“每一个足够大阶的{ X，Y } -free图都有一个2-因子”，并确定了使这一命题成立的对{ X，Y }。他们的结果是其中之一是{ X，Y } = { K 1，4，P 4 }。本文研究了r -连通{K1，k，P4} -free图中2-因子的存在性.证明了：若r ≥ 1，k ≥ 2，且G是一个最小度至少为k − 1的r -连通无{K1，k，P4}图，则G有一个2-因子最多有{k-r，1 }个分支，除非（k − 1）K2+（k − 2）K1 <$G <$（k − 1）K2 + Kk − 2 .最小度上的界是最好的。
. In [3], Faudree et al. considered the proposition “Every { X,Y } -free graph of sufficiently large order has a 2-factor,” and they determined those pairs { X,Y } which make this proposition true. Their result says that one of them is { X,Y } = { K 1 , 4 ,P 4 } . In this paper, we investigate the existence of 2-factors in r -connected { K 1 ,k ,P 4 } -free graphs. We prove that if r ≥ 1 and k ≥ 2, and if G is an r -connected { K 1 ,k ,P 4 } -free graph with minimum degree at least k − 1, then G has a 2-factor with at most max { k − r, 1 } components unless (k − 1 )K 2 + (k − 2 )K 1 ⊆ G ⊆ (k − 1 )K 2 + K k − 2 . The bound on the minimum degree is best possible.