Abstract
Letk and s be two positive integers with s≥3. LetG be a graph of ordern ≥sk. Writen =qk + r, 0 ≤r ≤k - 1. Suppose thatG has minimum degree at least (s - l)k. Then G containsk independent cyclesC 1,C 2,...,C k such thats ≤l(C i ) ≤q for 1 ≤i ≤r arnds ≤l(C i ) ≤q + 1 fork -r <i ≤k, where l(Ci) denotes the length ofC i .
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bollobás, B. Extremal Graph Theory, Academic Press, London (1978)
Corrádi, K., Hajnal, A.: On the maximal number of independent circuits in a graph, Acta Math. Acad. Sci. Hunger.14, 423–439 (1963)
Hajnal, A., Szemerédi, E.: Proof of a conjecture of Erdös, in “Combinatorial Theory and its Application”, Vol. II (P. Erdös, A. Renyi and V. Sós, eds), CoUoq. Math. Soc. J. Bolyai 4, North-Holland, Amsterdam, 1970, pp. 601–623
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Wang, H. Independent cycles with limited size in a graph. Graphs and Combinatorics 10, 271–281 (1994). https://doi.org/10.1007/BF02986677
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02986677