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:



DOI: http://dx.doi.org/10.30630/joiv.4.2.349

Abstract


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.


Keywords


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

Full Text:

PDF

References


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.




Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

__________________________________________________________________________
JOIV : International Journal on Informatics Visualization
ISSN 2549-9610  (print) | 2549-9904 (online)
Organized by Department of Information Technology - Politeknik Negeri Padang, and Institute of Visual Informatics - UKM and Soft Computing and Data Mining Centre - UTHM
Published by Department of Information Technology - Politeknik Negeri Padang
W : http://joiv.org
E : joiv@pnp.ac.id, hidra@pnp.ac.id, rahmat@pnp.ac.id

View JOIV Stats

Creative Commons License is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.