×

Covering the vertices of a graph by cycles of prescribed length. (English) Zbl 0693.05048

Summary: The main theorem of that paper is the following: let G be a graph of order n, of size at least \((n^ 2-3n+6)/2\). For any integers \(k,n_ 1,n_ 2,...,n_ k\) such that \(n=n_ 1+n_ 2+...+n_ k\) and \(n_ i\geq 3\), there exists a covering of the vertices of G by disjoint cycles \((C_ i)_{i=1...k}\) with \(| C_ i| =n_ i\), except when \(n=6\), \(n_ 1=3\), \(n_ 2=3\), and G is isomorphic to \(G_ 1\), the complement of \(G_ 1\) consisting of a \(C_ 3\) and a stable set of three vertices, or when \(n=9\), \(n_ 1=n_ 2=n_ 3=3\), and G is isomorphic to \(G_ 2\), the complement of \(G_ 2\) consisting of a complete graph on four vertices and a stable set of five vertices.
We prove an analogous theorem for bipartite graphs: let G be a bipartite balanced graph of order 2n, of size at least \(n^ 2-n+2\). For any integers \(s,n_ 1,n_ 2,...,n_ s\) with \(n_ i\geq 2\) and \(n=n_ 1+n_ 2+...+n_ s\), there exists a covering of the vertices of G by s disjoint cycles \(C_ i\), with \(| C_ i| =2n_ i\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Corradi, Acta Math. Sci. Hung. 14 pp 423– (1963)
[2] Dirac, Proc. London Math. Soc. 2 pp 69– (1952)
[3] El Zahar, Discrete Math. 50 pp 227– (1984)
[4] Moon, Isr. J. Math. 1 pp 163– (1963)
[5] Ore, Ann. Mat. Pura Applied 55 pp 315– (1961)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.