# Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts

Billington, Elizabeth J., Cavenagh, Nicholas J. and Smith, Benjamin R. (2010). Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts. In: Selected Papers from the 21st British Combinatorial Conference. 21st British Combinatorial Conference 2007, Reading, U.K., (241-254). 9-13 July 2007. doi:10.1016/j.disc.2008.09.003

Author Billington, Elizabeth J.Cavenagh, Nicholas J.Smith, Benjamin R. Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts 21st British Combinatorial Conference 2007 Reading, U.K. 9-13 July 2007 Selected Papers from the 21st British Combinatorial Conference   Check publisher's open access policy Discrete Mathematics   Check publisher's open access policy Amsterdam, The Netherlands Elsevier 2010 2008 Fully published paper 10.1016/j.disc.2008.09.003 0012-365X 310 2 241 254 13 2011 eng In 1998 Cavenagh [N.J. Cavenagh, Decompositions of complete tripartite graphs into k-cycles, Australas. J. Combin. 18 (1998) 193-200] gave necessary and sufficient conditions for the existence of an edge-disjoint decomposition of a complete equipartite graph with three parts, into cycles of some fixed length k. Here we extend this to paths, and show that such a complete equipartite graph with three partite sets of size m, has an edge-disjoint decomposition into paths of length k if and only if k divides 3m(2) and k < 3m. Further, extending to five partite sets, we show that a complete equipartite graph with five partite sets of size m has an edge-disjoint decomposition into cycles (and also into paths) of length k with k >= 3 if and only if k divides 10m(2) and k <= 5m for cycles (or k < 5m for paths). (C) 2008 Elsevier B.V. All rights reserved. Complete equipartite graphPath decompositionCycle decompositionLength C1 Confirmed Code UQ

 Document type: Conference Paper School of Mathematics and Physics Official 2011 Collection

 Versions Version Filter Type Sat, 21 Jan 2017, 08:06:37 EST Filtered Full
Citation counts: Cited 7 times in Thomson Reuters Web of Science Article | Citations Cited 7 times in Scopus Article | Citations Search Google Scholar Sun, 17 Jan 2010, 10:07:05 EST