Journal of the Operations Research Society of China ›› 2024, Vol. 12 ›› Issue (4): 1072-1087.doi: 10.1007/s40305-023-00473-5

Previous Articles     Next Articles

Disjoint Cycles and Degree Sum Condition in a Graph

Chun-Jiao Song, Yun Wang, Jin Yan   

  1. School of Mathematics, Shandong University, Jinan 250100, Shandong, China
  • Received:2022-08-02 Revised:2023-02-10 Online:2024-12-30 Published:2024-12-12
  • Contact: Jin Yan, Chun-Jiao Song, Yun Wang E-mail:yanj@sdu.edu.cn;chunjiao_sdu@163.com;wangyun_sdu@163.com
  • Supported by:
    This research was supported by the National Natural Science Foundation of China (No. 12071260).

Abstract: For an integer t, where t ≥ 2, let σt(G) denote the minimum degree sum of an independent set with t vertices in a graph G. We prove that for two integers k, t with k ≥ 3, t ≥ 4, every graph G with |V(G)| ≥ kt + 1.5k + t and σt(G) ≥ 2kt -t +1 contains k disjoint cycles. This result improves the theorem of Ma and Yan by optimizing the lower bound of |V(G)|. In addition, we also improve the theorem of Gould et al. for t = 4 and k ≥ 2.

Key words: Graph, Degree sum, Disjoint cycles

CLC Number: