Decomposing complete tripartite graphs into cycles of lengths 3 and 4
type: Item
instance of: scholarly article
title: Decomposing complete tripartite graphs into cycles of lengths 3 and 4
zbMATH Open document ID: 0930.05072
DOI: 10.1016/S0012-365X(99)90049-3
author: Elizabeth J. Billington
published in: Discrete Mathematics
publication date: 2000-01-30T00:00:00Z
review text: It is shown that the complete tripartite graph \(K_{r,s,t}\), \(r \leq s \leq t\), has an edge-disjoint decomposition into \(a\) cycles of length 3 and \(b\) cycles of length 4 if and only if (1) \(r,s,t\) have the same parity, (2) if \(r\) is even, or if \(r\) is odd and \(s-r \equiv 0 \pmod {4}\), then \(a \leq rs\), (3) if \(r\) is odd and \(s-r \equiv 2 \pmod {4}\), then \(a \leq rs-2\), (4) the value of \(a\) decreases from its maximum value in steps of size 4, down to 0 if \(r\) is even and to 1 if \(r\) is odd.
reviewed by: Katherine Heinrich
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1322005
zbMATH Keywords: decomposition
zbMATH Keywords: cycle
zbMATH Keywords: complete graph
MaRDI profile type: Publication
cites work: Decompositions of complete multipartite graphs into cycles of even length
cites work: On Alspach's conjecture
cites work: Q4026150
cites work: Q4858971
cites work: Decomposition of K//(m,n)(K*//(m,n)) into cycles (circuits) of length 2k
full work available at URL: s0012-365x(99)90049-3
OpenAlex ID: W4251623959
description: scientific article; zbMATH DE number 1322005