Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts (Q960919)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts |
scientific article |
Statements
Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts (English)
0 references
29 March 2010
0 references
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).
0 references
complete equipartite graph
0 references
path decomposition
0 references
cycle decomposition
0 references