On Degree Sum Conditions and Vertex-Disjoint Chorded Cycles
- PDF / 427,106 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 13 Downloads / 206 Views
(0123456789().,-volV) (0123456789().,-volV)
ORIGINAL PAPER
On Degree Sum Conditions and Vertex-Disjoint Chorded Cycles Bradley Elliott1
•
Ronald J. Gould2 • Kazuhide Hirohata3
Received: 20 December 2019 / Revised: 15 July 2020 Springer Japan KK, part of Springer Nature 2020
Abstract In this paper, we consider a general degree sum condition sufficient to imply the existence of k vertex-disjoint chorded cycles in a graph G. Let rt ðGÞ be the minimum degree sum of t independent vertices of G. We prove that if G is a graph of sufficiently large order and rt ðGÞ 3kt t þ 1 with k 1, then G contains k vertexdisjoint chorded cycles. We also show that the degree sum condition on rt ðGÞ is sharp. To do this, we also investigate graphs without chorded cycles. Keywords Vertex-disjoint chorded cycles Minimum degree sum Degree sequence Biconnected components Blocks
1 Introduction The study of cycles in graphs is a rich and an important area. One question of particular interest is to find conditions that guarantee the existence of k vertexdisjoint cycles. Let G be a graph. Corra´di and Hajnal [2] first considered a minimum degree condition to imply a graph must contain k vertex-disjoint cycles, proving that if jGj 3k and the minimum degree dðGÞ 2k, then G contains k vertex-disjoint cycles. For an integer t 1, let & Bradley Elliott [email protected] Ronald J. Gould [email protected] Kazuhide Hirohata [email protected] 1
Department of Mathematics, University of Kentucky, Lexington, KY 40506, USA
2
Department of Mathematics, Emory University, Atlanta, GA 30322, USA
3
Department of Industrial Engineering, Computer Science, National Institute of Technology, Ibaraki College, Hitachinaka 312-8508, Japan
123
Graphs and Combinatorics
( rt ðGÞ ¼ min
) X is an independent vertex degG ðvÞ : ; set of G with jXj ¼ t: v2X
X
and rt ðGÞ ¼ 1 when the independence number is t 1 or less. Enomoto [3] and Wang [11] independently extended the Corra´di and Hajnal result, requiring a weaker condition on the minimum degree sum of any two non-adjacent vertices. They proved that if jGj 3k and r2 ðGÞ 4k 1, then G contains k vertex-disjoint cycles. In 2006, Fujita et al. [5] proved that if jGj 3k þ 2 and r3 ðGÞ 6k 2, then G contains k vertex-disjoint cycles, and in [7], this result was extended to r4 ðGÞ 8k 3. Recently, Ma and Yan [10] proved a conjecture from [7] by showing that if G has sufficiently large order and rt ðGÞ 2kt t þ 1, then G contains k vertex-disjoint cycles. A chord of a cycle is an edge between two non-consecutive vertices of the cycle. An extension of the study of vertex-disjoint cycles is that of vertex-disjoint chorded cycles. We say a cycle is chorded if it contains at least one chord. In 2008, Finkel [4] proved the following result on the existence of k vertex-disjoint chorded cycles which can be viewed as an extension of the Corra´di and Hajnal result. Theorem 1 (Finkel [4]) Let k 1 be an integer. If G is a graph of order at least 4k and dðGÞ 3k, then G co
Data Loading...
