Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts
type: Item
instance of: scholarly article
title: Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts
zbMATH Open document ID: 1200.05135
author: Elizabeth J. Billington
author: Nicholas J. Cavenagh
author: Benjamin R. Smith
published in: Discrete Mathematics
publication date: 2010-03-29T00:00:00Z
review text: It is proved that a complete tripartite graph with all 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\). This extends a previous result on decomposition into cycles of lengths \(k\) by \textit{N. J. Cavenagh} [``Decompositions of complete tripartite graphs into \(k\)-cycles'', Australas. J. Comb. 18, 193--200 (1998; Zbl 0924.05051)]. It is also proved that a complete multipartite graph with five partite sets of size \(m\) has an edge-disjoint decomposition into paths (and also cycles) of length \(k\) with \(k\geq 3\) if and only if \(k\) divides \(10m^2\) and \(k<5m\) (or \(k\leq 5m\) for cycles).
reviewed by: Dalibor Fronček
Mathematics Subject Classification ID: 05C51
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5687553
zbMATH Keywords: complete equipartite graph
zbMATH Keywords: path decomposition
zbMATH Keywords: cycle decomposition
MaRDI profile type: Publication
full work available at URL: j.disc.2008.09.003
OpenAlex ID: W4231988724
cites work: Cycle decompositions of \(K_n\) and \(K_n-I\)
cites work: Path and cycle decompositions of complete equipartite graphs: Four parts
cites work: Q4222083
cites work: Decompositions of complete multipartite graphs into cycles of even length
cites work: \(C_{p}\)-decompositions of some regular graphs
cites work: Cycle decompositions. III: Complete graphs and fixed length cycles.
cites work: Decomposing complete equipartite graphs into cycles of length2p
cites work: Decomposition of K//(m,n)(K*//(m,n)) into cycles (circuits) of length 2k
cites work: Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs
DOI: 10.1016/J.DISC.2008.09.003
description: scientific article; zbMATH DE number 5687553