zbMATH — the first resource for mathematics

On vertex-disjoint cycles and degree sum conditions. (English) Zbl 1372.05111
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\).

05C38 Paths and cycles
05C07 Vertex degrees
05C35 Extremal problems in graph theory
Full Text: DOI
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.