Pairwise compatible Hamilton decompositions of \(K_n\)
type: Item
instance of: scholarly article
title: Pairwise compatible Hamilton decompositions of \(K_n\)
zbMATH Open document ID: 0901.05075
published in: Journal of Combinatorial Theory. Series A
publication date: 1998-11-09T00:00:00Z
review text: A Hamilton decomposition (respectively Hamilton path decomposition) of a complete graph is a partition of its edges into Hamilton cycles (respectively paths). Two such decompositions are compatible if they do not use the same pair of edges at any vertex. A simple counting argument reveals that there are at most \(2k-1\) pairwise compatible Hamilton decompositions of \(K_{2k+1}\) (respectively Hamilton path decompositions of \(K_{2k}\)). Kotzig asked whether this bound can be achieved for some \(k\) (it cannot for small values of \(k\)). This remains open, and in fact very little was known about lower bounds on the possible numbers of pairwise compatible decompositions. The author gives constructions showing that there are at least \(2k-2\) pairwise compatible Hamilton path decompositions of \(K_{2k}\). (This is just one short of the maximum possible number, as noted above.) For Hamilton decompositions of \(K_{2k+1}\), she also gives constructions providing lower bounds, which are roughly a third of \(2k-1\) when \(k\) is odd or \(2k-1\) is prime, and somewhat smaller otherwise.
reviewed by: Pavol Hell
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1051478
zbMATH Keywords: graph decompositions
zbMATH Keywords: Hamilton decompositions
zbMATH Keywords: compatible decompositions
author: Helen Verrall
MaRDI profile type: Publication
full work available at URL: jcta.1997.2777
OpenAlex ID: W2085858763
cites work: Finite topologies and Hamiltonian paths
cites work: Dudeney's round table problem
cites work: A Construction of a perfect set of Euler tours of K2k+1
cites work: A solution of Dudeney's round table problem for an even number of people
cites work: Exact coverings of 2-paths by Hamilton cycles
cites work: Q3855185
cites work: Q3874209
cites work: Q4222136
DOI: 10.1006/JCTA.1997.2777
description: scientific article; zbMATH DE number 1051478