Fair Hamilton decompositions of complete multipartite graphs
type: Item
instance of: scholarly article
title: Fair Hamilton decompositions of complete multipartite graphs
zbMATH Open document ID: 1024.05072
author: C. D. Leach
author: C. A. Rodger
published in: Journal of Combinatorial Theory. Series B
publication date: 2002-12-10T00:00:00Z
review text: A fair Hamilton decomposition of the complete multipartite graph \(G\) is a set of Hamilton cycles in \(G\) whose edges partition the edges of \(G\) in such a way that, for each pair of parts and for each pair of Hamiliton cycles \(H_1\) and \(H_2\), the difference in the number of edges in \(H_1\) and \(H_2\) joining vertices in these two parts is at most one. The authors prove the following theorem: There exists a fair Hamilton decomposition of \(K_{a_1,\ldots,a_p}\) if and only if \(a_1 = \cdots = a_p = m\) and \((p-1)m\) is even. The proof is constructive using graph homomorphisms which preserve the number of edges, but may identify adjacent vertices thereby generating (multiple) loops, which sometimes is called amalgamation.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1843834
zbMATH Keywords: graph homomorphisms
zbMATH Keywords: Hamilton cycles
reviewed by: Ulrich Knauer
MaRDI profile type: Publication
full work available at URL: jctb.2001.2104
OpenAlex ID: W2070602317
cites work: Balanced Gray codes
cites work: Q5650698
cites work: A sufficient condition for equitable edge-colourings of simple graphs
cites work: Hamiltonian decompositions of complete graphs
cites work: Hamiltonian decompositions of complete regular s-partite graphs
cites work: The embedding of partial triple systems when 4 divides \(\lambda\)
cites work: Nondisconnecting disentanglements of amalgamated 2-factorizations of complete multipartite graphs
cites work: The Solution of a Timetabling Problem
cites work: Amalgamations of almost regular edge-colourings of simple graphs
DOI: 10.1006/JCTB.2001.2104
description: scientific article; zbMATH DE number 1843834