zbMATH — the first resource for mathematics

Covering the vertices of a digraph by cycles of prescribed length. (English) Zbl 0764.05070
Summary: Let \(D\) be a strong digraph with \(n\) vertices and at least \((n-1)(n-2)+3\) arcs. For any integers \(k,n_ 1,n_ 2,\dots,n_ k\) such that \(n=n_ 1+n_ 2+\cdots+n_ k\) and \(n_ 1\geq 3\), there exists a covering of the vertices of \(D\) by disjoint directed cycles of length \(n_ 1,n_ 2,\dots,n_ k\) except in two cases: Case 1: \(n=6\); \(n_ 1=n_ 2=3\) and \(D\) contains a stable set with 3 vertices. Case 2: \(n=9\); \(n_ 1=n_ 2=n_ 3=3\) and \(D\) contains a stable set with 4 vertices.

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
Full Text: DOI
[1] Amar, D., Orientation de cycles dans un graphe orienté, Thèse université de Bordeaux I, (1985), chp. III
[2] D. Amar, I. Fournier and A. Germa, Covering the vertices of a graph by cycles of prescribed length, Graph Theory, to appear. · Zbl 0693.05048
[3] D. Amar and A. Raspaud, Covering the vertices of a digraph by cycles of prescribed length. Rapport de Recherche no 8701, Université de Bordeaux I, U.E.R. Math. et Informatique. · Zbl 0764.05070
[4] Benhocine, A.; Wojda, A.P., On the existence of D(n, p) in directed graphs, (), 47-52 · Zbl 0523.05039
[5] Bermond, J.C.; Germa, A.; Heydeman, M.C.; Sotteau, D., Chemins et circuits dans LES graphes orientés, (), 293-309 · Zbl 0453.05032
[6] Chvátal, V., On Hamilton’s ideals, J. combin. theory ser. B, 12, 163-168, (1972) · Zbl 0213.50803
[7] Corradi, 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
[8] Elzahar, M.H., On circuits in graphs, Discrete math., 50, 227-230, (1984) · Zbl 0548.05037
[9] Heydeman, M.C.; Sotteau, D.; Thomassen, C., Orientations of Hamiltonian cycles in digraphs, Ars combin., 3-8, (1982) · Zbl 0503.05036
[10] Ore, O., Hamilton connected graphs, J. math. pures appl., 42, 21-27, (1963) · Zbl 0106.37103
[11] Wojda, A.P., Orientation of Hamiltonian digraphs in large digraphs, J. graph theory, 10, 211-218, (1986) · Zbl 0593.05033
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.