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.
Title of paper Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts
Conference name 21st British Combinatorial Conference 2007
Conference location Reading, U.K.
Conference dates 9-13 July 2007
Proceedings title Selected Papers from the 21st British Combinatorial Conference   Check publisher's open access policy
Journal name Discrete Mathematics   Check publisher's open access policy
Place of Publication Amsterdam, The Netherlands
Publisher Elsevier
Publication Year 2010
Year available 2008
Sub-type Fully published paper
DOI 10.1016/j.disc.2008.09.003
ISSN 0012-365X
Volume 310
Issue 2
Start page 241
End page 254
Total pages 13
Language eng
Formatted Abstract/Summary
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.
Keyword Complete equipartite graph
Path decomposition
Cycle decomposition
Length
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Conference Paper
Collections: School of Mathematics and Physics
Official 2011 Collection
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 8 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 7 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Sun, 17 Jan 2010, 10:07:05 EST