“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 8280
School of Mathematics
  Title:   Commuting decompositions of complete graphs
  Author(s):  S. Akbari (Joint with A. Herman)
  Status:   Published
  Journal: J. Combin. Des.
  Vol.:  15
  Year:  2007
  Pages:   133-142
  Supported by:  IPM
  Abstract:
We say that two graph G and H with the same vertex set commute if their adjacency matrices commute. In this article, we show that for any natural number r, the complete multigraph Krn is decomposable into commuting perfect matchings if and only if n is a 2-power. Also, it is shown that the complete graph Kn is decomposable into commuting Hamilton cycles if and only if n is a prime number.

Download TeX format
back to top
scroll left or right