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.
Chun-Jiao Song, Yun Wang, Jin Yan
. Disjoint Cycles and Degree Sum Condition in a Graph[J]. Journal of the Operations Research Society of China, 2024
, 12(4)
: 1072
-1087
.
DOI: 10.1007/s40305-023-00473-5
[1] Diestel, R.: Graph Theory, 5th edn. Springer, Berlin (2018)
[2] Erdős, P., Pósa, L.: On the maximal number of disjoint circuits of a graph. Pul. Math. 9, 3-12(1962)
[3] Corrádi, K., Hajnal, A.: On the maximal number of independent circuits in a graph. Acta Math. 14, 423-439(1963)
[4] Gould, R.J., Hirohata, K., Keller, A.: On vertex disjoint cycles and degree sum conditions. Discrete Math. 341, 203-212(2018)
[5] Ma, F., Yan, J.: The confirmation of a conjecture on disjoint cycles in a graph. Discrete Math. 341, 2903-2911(2018)
[6] Chiba, S., Yamashita, T.: Degree conditions for the existence of vertex-disjoint cycles and paths: A survey. Graphs Combin. 34, 1-83(2018)
[7] Jiao, Z., Wang, H., Yan, J.: Disjoint cycles in graphs with distance degree sum conditions. Discrete Math. 340, 1203-1209(2017)
[8] Wang, H.: On the maximum number of independent cycles in a bipartite graph. J Combin. Theory. 67, 152-164(1996)
[9] Wang, H.: Disjoint long cycles in a graph. Sci. China Ser. A Math. 56, 1983-1998(2013)
[10] Yan, J., Gao, Y.: On Enomoto’s problems in a bipartite graph. Sci. China Ser. A Math. 52, 1947-1954(2009)
[11] Fujita, S., Matsumura, H., Tsugaki, M., Yamashita, T.: Degree sum conditions and vertex disjoint cycles in a graph. Aust. J Combin. 35, 237-251(2006)
[12] Brandt, S., Chen, G., Gould, R.J., lesniak, L.: Degree condition for 2-factors. J. Graph Theory. 24, 165-173(1997)
