Cycles

From G-designs

Jump to: navigation, search

Relevant articles: [1], [2], [3], [4], [5].

Contents

[hide]

Cycles


The graphs considered in this section are cycles. The cycle with m vertices is denoted by C_m.


Spectrum Results



The spectrum problem for m-cycles is completely solved for all m, see [2] and [4].

Theorem 1 [2], [4]

Let m\geq 3. There exists a C_m-design of order n if and only if

  • n=1 or n\geq m;
  • n is odd; and
  • n(n-1)\equiv 0 \,({\rm mod \ }2m).



Notes


  • C_3-designs are K_3-designs.
  • C_3-designs are Steiner triple systems.



References


  1. ↑ Adams, P., Bryant, D., and Buchanan, M. A survey on the existence of G-designs, J. Combin. Des. 16, 373–410 (2008).
  2. ↑ 2.0 2.1 2.2 Alspach, B. and Gavlas, H. Cycle decompositions of K_n and K_n-I, J. Combin. Theory Ser. B, 81, 77–99 (2001).
  3. ↑ Hoffman, D. G., Lindner, C. C., and Rodger, C. A. On the construction of odd cycle systems, J. Graph Theory, 13, 417–426 (1989).
  4. ↑ 4.0 4.1 4.2 Šajna, M. Cycle decompositions. III. Complete graphs and fixed length cycles, J. Combin. Des. 10, 27–78 (2002).
  5. ↑ Sotteau, D. Decomposition of K_m,n (K^^\ast _m,n) into cycles (circuits) of length 2k, J. Combin. Theory Ser. B, 30, 75–81 (1981).