Decompositions of Complete Multigraphs into Cyclic Designs

Mowafaq Alqadri - Universiti Utara Malaysia, Sintok, Kedah, Malaysia
Haslinda Ibrahim - Universiti Utara Malaysia, Sintok, Kedah, Malaysia
Sharmila Karim - Universiti Utara Malaysia, Sintok, Kedah, Malaysia

Citation Format:



Let  and  be positive integer,  denote a complete multigraph. A decomposition of a graph  is a set of subgraphs of  whose edge sets partition the edge set of . The aim of this paper, is to decompose a complete multigraph  into cyclic -cycle system according to specified conditions. As the main consequence, construction of decomposition of  into cyclic Hamiltonian wheel system, where , is also given. The difference set method is used to construct the desired designs.


Cyclic design; Hamiltonian cycle; Near four factor; Wheel graph.

Full Text:



S. L. Wu and H. C. Lu, “Cyclically decomposing the complete graph into cycles with pendent edgesâ€. ARS COMBINATORIA-WATERLOO THEN WINNIPEG, vol. 86, no. 217, 2008.

B. R. Smith, “Cycle decompositions of complete multigraphs,†Journal of Combinatorial Designs, vol. 18, no. 2, pp.85-93, 2010.

D. Bryant, D. Horsley, B. Maenhaut and B. R. Smith, “Cycle decompositions of complete multigraphsâ€, Journal of Combinatorial Designs, vol. 19, no. 1, pp. 42-69, 2011.

B. Alspach and H. Gavlas, “Cycle decompositions of K_n and K_n- I,â€. Journal of Combinatorial Theory, Series B, vol. 81, no. 1, pp. 77-99, 2001.

M. Šajna, “Cycle decompositions III: complete graphs and fixed length cycles,†Journal of Combinatorial Designs, vol. 10, no. 1, pp. 27-78, 2002.

M. J. Colbourn and C. J. Colbourn, “Cyclic block designs with block size 3,†European Journal of Combinatorics, vol, 2, no. 1, pp. 21-26, 1981.

M. Buratti and A. Del Fra, “Cyclic Hamiltonian cycle systems of the complete graph,†Discrete mathematics, vol. 279, no. 1, pp. 107-119, 2004.

F. Beggas, M. Haddad and H. Kheddouci, “Decomposition of Complete Multigraphs Into Stars and Cycles,†Discussiones Mathematicae Graph Theory, vol. 35, no. 4, pp. 629-639, 2015.â€

R. S. Rees, “The spectrum of triangle-free regular graphs containing a cut vertex,†Australasian Journal of Combinatorics, vol. 26, pp. 135-14, 2002.

S. L. Wu and H. L. Fu, “Cyclic mâ€cycle systems with m≤ 32 or m= 2q with q a prime power,â€. Journal of Combinatorial Designs, vol. 14, no. 1, pp. 66-81, 2006

M. Buratti, “A description of any regular or 1-rotational design by difference methods,†Booklet of the abstracts of Combinatorics, pp. 35-52, 2000.

S. Pemmaraju and S. Skiena, “Cycles, stars, and wheels,†Computational Discrete Mathematics Combinatiorics and Graph Theory in Mathematica, pp. 284-249, 2003.