Symmetric Hamilton Cycle Decompositions of Complete Multigraphs

V. Chitra; A. Muthusamy

Discussiones Mathematicae Graph Theory (2013)

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

Abstract

top
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

How to cite

top

V. 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. [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. [2] B. Alspach, The wonderful Walecki construction, Bull. Inst. Combin. Appl. 52 (2008) 7-20. Zbl1157.05035
  3. [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] 
  4. [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
  5. [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
  6. [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
  7. [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] 
  8. [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
  9. [10] D.E. Lucas, Recreations Mathematiques, Vol.2 (Gauthiers Villars, Paris, 1982). Zbl0088.00101

NotesEmbed ?

top

You must be logged in to post comments.