On a Sharp Degree Sum Condition for Disjoint Chorded Cycles in Graphs
On a Sharp Degree Sum Condition for Disjoint Chorded Cycles in Graphs
复制标题
DOI：
10.1007/s00373-010-0901-5
复制
发表时间：
2010-03
影响因子：
0.7
通讯作者：
S. Chiba;S. Fujita;Yunshu Gao;Guojun Li
中科院分区：
文献类型：
--
作者：
S. Chiba;S. Fujita;Yunshu Gao;Guojun Li
设G是阶至少为3r+ 4s的图。在Bialostocki等人中。（离散数学308：5886-5890，2008），证明了如果G的最小度至少是2 r + 3s，则G包含r + s个顶点不相交的圈的集合，使得其中s个是弦圈，并且他们证明了该猜想对于r = 0，s= 2和s = 1都是正确的。在本文中，我们通过证明以下更强的陈述完全解决了这个猜想：如果两个不相邻顶点的最小度和至少为4 r + 6s−1，则G包含r + s个顶点不相交的圈的集合，使得其中s个是弦圈。
Letrandsbe nonnegative integers, and letGbe a graph of order at least 3r+ 4s. In Bialostocki et al. (Discrete Math 308:5886–5890, 2008), conjectured that if the minimum degree ofGis at least 2r+ 3s, thenGcontains a collection ofr+svertex-disjoint cycles such thatsof them are chorded cycles, and they showed that the conjecture is true forr= 0,s= 2 and fors= 1. In this paper, we settle this conjecture completely by proving the following stronger statement; if the minimum degree sum of two nonadjacent vertices is at least 4r+ 6s−1, thenGcontains a collection ofr+svertex-disjoint cycles such thatsof them are chorded cycles.