Path and cycle decompositions of complete equipartite graphs: Four parts

Billington, Elizabeth J., Cavenagh, Nicholas J. and Smith, Benjamin R. (2009) Path and cycle decompositions of complete equipartite graphs: Four parts. Discrete Mathematics, 309 10: 3061-3073. doi:10.1016/j.disc.2008.08.009


Author Billington, Elizabeth J.
Cavenagh, Nicholas J.
Smith, Benjamin R.
Title Path and cycle decompositions of complete equipartite graphs: Four parts
Journal name Discrete Mathematics   Check publisher's open access policy
ISSN 0012-365X
1872-681X
Publication date 2009-05-28
Year available 2008
Sub-type Article (original research)
DOI 10.1016/j.disc.2008.08.009
Volume 309
Issue 10
Start page 3061
End page 3073
Total pages 13
Editor D. B. West
Place of publication Amsterdam, The Netherlands
Publisher Elsevier
Collection year 2011
Language eng
Subject C1
970101 Expanding Knowledge in the Mathematical Sciences
010104 Combinatorics and Discrete Mathematics (excl. Physical Combinatorics)
Formatted abstract
We show that a complete equipartite graph with four partite sets has an edge-disjoint decomposition into cycles of length k if and only if k≥3, the partite set size is even, k divides the number of edges in the equipartite graph and the total number of vertices in the graph is at least k. We also show that a complete equipartite graph with four even partite sets has an edge-disjoint decomposition into paths with k edges if and only if k divides the number of edges in the equipartite graph and the total number of vertices in the graph is at least k+1.
Keyword Complete equipartite graph
Path decomposition
Cycle decomposition
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collection: School of Mathematics and Physics
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 9 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 10 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 04 Aug 2009, 23:24:50 EST by Marie Grove on behalf of School of Mathematics & Physics