On vertex-disjoint cycles and degree sum conditions. (English) Zbl 1372.05111

Gould, Ronald J.; Hirohata, Kazuhide; Keller, Ariel

Discrete Math. 341, No. 1, 203-212 (2018).

Summary: This paper considers a degree sum condition sufficient to imply the existence of \(k\) vertex-disjoint cycles in a graph \(G\). For an integer \(t\), let \(\sigma_t(G)\) be the smallest sum of degrees of t independent vertices of \(G\). We prove that if \(G\) has order at least \(7k+1\) and \(\sigma_4(G)\geq 8k-3\), with \(k\), then \(G\) contains \(k\) vertex-disjoint cycles. We also show that the degree sum condition on \(\sigma_4(G)\) is sharp and conjecture a degree sum condition on \(\sigma_t(G)\) sufficient to imply \(G\) contains \(k\) vertex-disjoint cycles for \(k\geq 2\).

MSC:

05C38	Paths and cycles
05C07	Vertex degrees
05C35	Extremal problems in graph theory

Keywords:

vertex-disjoint cycles; minimum degree sum; degree sequence

References:

[1]	Corrádi, K.; Hajnal, A., On the maximal number of independent circuits in a graph, Acta Math. Acad. Sci. Hungar., 14, 423-439, (1963) · Zbl 0118.19001
[2]	Enomoto, H., On the existence of disjoint cycles in a graph, Combinatorica, 18, 4, 487-492, (1998) · Zbl 0924.05041
[3]	Fujita, S.; Matsumura, H.; Tsugaki, M.; Yamashita, T., Degree sum conditions and vertex-disjoint cycles in a graph, Australas. J. Combin., 35, 237-251, (2006) · Zbl 1096.05029
[4]	Gould, R. J., Graph Theory, (2012), Dover Pub. Inc. Mineola, N.Y.
[5]	Justesen, P., On independent circuits in finite graphs and a conjecture of Erdős and Pósa, Ann. Discrete Math., 41, 299-306, (1989) · Zbl 0673.05065
[6]	Wang, H., On the maximum number of independent cycles in a graph, Discrete Math., 205, 1-3, 183-190, (1999) · Zbl 0936.05063