# Symmetric Hamilton Cycle Decompositions of Complete Multigraphs

Discussiones Mathematicae Graph Theory (2013)

- Volume: 33, Issue: 4, page 695-707
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topV. Chitra, and A. Muthusamy. "Symmetric Hamilton Cycle Decompositions of Complete Multigraphs." Discussiones Mathematicae Graph Theory 33.4 (2013): 695-707. <http://eudml.org/doc/267866>.

@article{V2013,

abstract = {Let n ≥ 3 and ⋋ ≥ 1 be integers. Let ⋋Kn denote the complete multigraph with edge-multiplicity ⋋. In this paper, we show that there exists a symmetric Hamilton cycle decomposition of ⋋K2m for all even ⋋ ≥ 2 and m ≥ 2. Also we show that there exists a symmetric Hamilton cycle decomposition of ⋋K2m − F for all odd ⋋ ≥ 3 and m ≥ 2. In fact, our results together with the earlier results (by Walecki and Brualdi and Schroeder) completely settle the existence of symmetric Hamilton cycle decomposition of ⋋Kn (respectively, ⋋Kn − F, where F is a 1-factor of ⋋Kn) which exist if and only if ⋋(n − 1) is even (respectively, ⋋(n − 1) is odd), except the non-existence cases n ≡ 0 or 6 (mod 8) when ⋋ = 1},

author = {V. Chitra, A. Muthusamy},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {complete multigraph; 1-factor; symmetric Hamilton cycle; decomposition.; decomposition},

language = {eng},

number = {4},

pages = {695-707},

title = {Symmetric Hamilton Cycle Decompositions of Complete Multigraphs},

url = {http://eudml.org/doc/267866},

volume = {33},

year = {2013},

}

TY - JOUR

AU - V. Chitra

AU - A. Muthusamy

TI - Symmetric Hamilton Cycle Decompositions of Complete Multigraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2013

VL - 33

IS - 4

SP - 695

EP - 707

AB - Let n ≥ 3 and ⋋ ≥ 1 be integers. Let ⋋Kn denote the complete multigraph with edge-multiplicity ⋋. In this paper, we show that there exists a symmetric Hamilton cycle decomposition of ⋋K2m for all even ⋋ ≥ 2 and m ≥ 2. Also we show that there exists a symmetric Hamilton cycle decomposition of ⋋K2m − F for all odd ⋋ ≥ 3 and m ≥ 2. In fact, our results together with the earlier results (by Walecki and Brualdi and Schroeder) completely settle the existence of symmetric Hamilton cycle decomposition of ⋋Kn (respectively, ⋋Kn − F, where F is a 1-factor of ⋋Kn) which exist if and only if ⋋(n − 1) is even (respectively, ⋋(n − 1) is odd), except the non-existence cases n ≡ 0 or 6 (mod 8) when ⋋ = 1

LA - eng

KW - complete multigraph; 1-factor; symmetric Hamilton cycle; decomposition.; decomposition

UR - http://eudml.org/doc/267866

ER -

## References

top- [1] J. Akiyama, M. Kobayashi and G. Nakamura, Symmetric Hamilton cycle decompositions of the complete graph, J. Combin. Des. 12 (2004) 39-45. doi:10.1002/jcd.10066[Crossref] Zbl1031.05100
- [2] B. Alspach, The wonderful Walecki construction, Bull. Inst. Combin. Appl. 52 (2008) 7-20. Zbl1157.05035
- [3] J. Bosák, Decompositions of Graphs (Kluwer Academic Publishers, 1990). 4] R.A. Brualdi and M.W. Schroeder, Symmetric Hamilton cycle decompositions of complete graphs minus a 1-factor , J. Combin. Des. 19 (2011) 1-15. doi:10.1002/jcd.20257[Crossref]
- [5] M. Buratti, S. Capparelli and A. Del Fra, Cyclic Hamiltonian cycle systems of the -fold complete and cocktail party graph, European J. Combin. 31 (2010) 1484-1496. doi:10.1016/j.ejc.2010.01.004[Crossref][WoS] Zbl1222.05141
- [6] M. Buratti and A. Del Fra, Cyclic Hamiltonian cycle systems of the complete graph, Discrete Math. 279 (2004) 107-119. doi:10.1016/S0012-365X(03)00267-X[Crossref][WoS] Zbl1034.05030
- [7] M. Buratti and F. Merola, Dihedral Hamiltonian cycle system of the cocktail party graph, J. Combin. Des. 21 (2013) 1-23. doi:10.1002/jcd.21311[WoS][Crossref] Zbl1260.05118
- [8] A.J.W. Hilton, Hamiltonian decompositions of complete graphs, J. Combin. Theory (B) 36 (1984) 125-134. doi:10.1016/0095-8956(84)90020-0[Crossref]
- [9] H. Jordon and J. Morris, Cyclic hamiltonian cycle systems of the complete graph minus a 1-factor , Discrete Math. 308 (2008) 2440-2449. doi:10.1016/j.disc.2007.05.009[Crossref][WoS] Zbl1172.05332
- [10] D.E. Lucas, Recreations Mathematiques, Vol.2 (Gauthiers Villars, Paris, 1982). Zbl0088.00101

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.