Czechoslovak Mathematical Journal, Vol. 57, No. 2, pp. 523-551, 2007

# Decomposing complete tripartite graphs into closed trails of arbitrary lengths

## Elizabeth J. Billington, Nicholas J. Cavenagh

Elizabeth J. Billington, Centre for Discrete Mathematics and Computing, Department of Mathematics, The University of Queensland, Brisbane, Qld 4072, Australia, e-mail: ejb@maths.uq.edu.au; Nicholas J. Cavenagh, Institute for Theoretical Computer Science ITI, Charles University, Malostranske namesti 25, 118 00 Praha 1, Czech Republic, e-mail: nicholas$_$cavenagh@yahoo.co.uk

Abstract: The complete tripartite graph $K_{n,n,n}$ has $3n^2$ edges. For any collection of positive integers $x_1,x_2,\dots,x_m$ with $\sum_{i=1}^m x_i=3n^2$ and $x_i\ge3$ for $1\le i\le m$, we exhibit an edge-disjoint decomposition of $K_{n,n,n}$ into closed trails (circuits) of lengths $x_1,x_2,\dots,x_m$.

Keywords: cycles, decomposing complete tripartite graphs

Classification (MSC 2000): 05C70, 05C38

Full text available as PDF (smallest), as compressed PostScript (.ps.gz) or as raw PostScript (.ps).