Commuting decompositions of complete graphs |
| |
Authors: | Saieed Akbari Allen Herman |
| |
Affiliation: | 1. Institute for Studies in Theoretical Physics and Mathematics, P. O. Box 19395‐5746, Tehran, Iran;2. Department of Mathematical Sciences, Sharif University of Technology, P. O. Box 11365‐9415, Tehran, Iran;3. Department of Mathematics and Statistics, University of Regina, Regina, Saskatchewan, Canada S4S 0A2 |
| |
Abstract: | We say that two graphs 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 K 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. © 2006 Wiley Periodicals, Inc. J Combin Designs |
| |
Keywords: | adjacency matrices of graphs graph decompositions |
|
|