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:; Nicholas J. Cavenagh, Institute for Theoretical Computer Science ITI, Charles University, Malostranske namesti 25, 118 00 Praha 1, Czech Republic, e-mail: nicholas$_$

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).

Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at
Subscribers of Springer need to access the articles on their site, which is

[Previous Article] [Next Article] [Contents of This Number] [Contents of Czechoslovak Mathematical Journal]