Premium
Commuting decompositions of complete graphs
Author(s) -
Akbari Saieed,
Herman Allen
Publication year - 2007
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.20112
Subject(s) - combinatorics , mathematics , vertex (graph theory) , prime power , graph , discrete mathematics , adjacency list , multigraph , prime (order theory)
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 n ris decomposable into commuting perfect matchings if and only if n is a 2‐power. Also, it is shown that the complete graph K n is decomposable into commuting Hamilton cycles if and only if n is a prime number. © 2006 Wiley Periodicals, Inc. J Combin Designs