×
Hoffman, D. G.; Lindner, C. C.; Rodger, C. A.

On the construction of odd cycle systems. (English) Zbl 0704.05031

J. Graph Theory 13, No. 4, 417-426 (1989).
Let \(K_ n\) be a complete nonoriented graph. A cycle system of order n is defined as a decomposition of the edge set of \(K_ n\) into disjoint cycles of the length k. The necessary conditions for \(K_ n\) to be decomposable into k-cycles are \(n\geq k,\) n is odd, \(2k| n(n-1).\) (*)
In the paper there is investigated the case of odd k. It is shown that necessary conditions (*) are also sufficient if and only if each admissible graph \(K_ n\) (satisfying (*) for \(k\leq n<3k)\) is decomposable into k-cycles. The cases of decompositions into 15-cycles and 21-cycles are solved completely.
Reviewer: L.Niepel

Cited in 2 Reviews
Cited in 37 Documents

MSC:

05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

complete graph; k-cycles; decompositions
PDF BibTeX XML Cite
\textit{D. G. Hoffman} et al., J. Graph Theory 13, No. 4, 417--426 (1989; Zbl 0704.05031)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Alspach, Ann. Discrete Math. 9 pp 155– (1980)
[2] Bermond, Congressus Numerantium 15 pp 53– (1975)
[3] Bermond, Ars. Combinat. 5 pp 293– (1978)
[4] and , Cycle and circuit designs: Odd Case. Beitrage zur Graphentheorie und deren Anwendungen. Proc. Colloq. Oberhof Illmenau (1978) 11–32.
[5] and , Graph Theory with Applications, North Holland, (1976). · Zbl 1226.05083
[6] The intersection problem for pentagon systems. Ph.D. thesis, Auburn University (1987).
[7] Häggkvist, Ann. Discrete Math. 27 pp 227– (1985)
[8] Kotzig, Mat.- Fyz. Cas 15 pp 227– (1965)
[9] Rosa, Mat.-Fyz. Cas 16 pp 349– (1966)
[10] Rosa, Casopis Pest. Math. 91 pp 53– (1966)
[11] Rosa, Discrete Math. 12 pp 269– (1975)
[12] Décompositions de graphes et hypergraphes. Thèses de l’Université Paris-Sud (1980).
[13] Sotteau, J. Combinat. Theory B 29 pp 75– (1981)
[14] Stern, Boll. Un. Math. Ital. A(5) 17 pp 109– (1980)
[15] Vizing, Discrete Analiz. 3 pp 25– (1964)
[16] Wilson, Math. Centre Tracts 55 pp 18– (1974)
[17] Wilson, Congresses Numerantium 15 pp 647– (1975)
[18] Wilson, J. Combinat. Theory A 13 pp 246– (1972)
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.