Decompositions into 2-regular subgraphs and equitable partial cycle decompositions
type: Item
instance of: scholarly article
title: Decompositions into 2-regular subgraphs and equitable partial cycle decompositions
zbMATH Open document ID: 1059.05083
author: Daniel Horsley
author: Darryn Bryant
author: Barbara Maenhaut
published in: Journal of Combinatorial Theory. Series B
publication date: 2005-02-09T00:00:00Z
review text: The reviewer [Research problems, Problem 3, Discrete Math. 36, 333 (1981)] posed the following question in 1981. Given positive integers \(m_1,m_2,\dots,m_t\), all of which are at least 3 and at most \(n\), where \(n\) is odd, whose sum is \({{n}\choose{2}}\), is it possible to decompose the complete graph \(K_n\) into cycles of lengths \(m_1,m_2,\dots,m_t\)? The analogous problem for \(n\) even is that the sum should be \(n(n-2)/2\) and the target graph should be \(K_n\) with a 1-factor removed. We are a long way from a solution at this point in time. Outside of isolated special cases, not much is known. In a related direction, \textit{P. Balister} [Comb. Probab. Comput. 10, 463--499 (2001; Zbl 1113.05309)] proved the analogous result for even subgraphs (every vertex has even valency). The present paper takes Balister's result one step closer to the original problem. The authors prove that \(K_n\) and \(K_n-I\) can be decomposed into 2-factors with \(m_1,m_2,\dots, m_t\) edges, respectively. The authors also show that a partial cycle decomposition of \(K_n\) implies an equitable partial cycle decomposition with cycles of the same lengths.
reviewed by: Brian Alspach
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 2132708
zbMATH Keywords: Alspach conjecture
zbMATH Keywords: 2-factor
zbMATH Keywords: decomposition
zbMATH Keywords: equitable cycle decomposition
MaRDI profile type: Publication
full work available at URL: j.jctb.2004.06.002
OpenAlex ID: W2094447546
cites work: On Alspach's conjecture with two even cycle lengths
cites work: Cycle decompositions of \(K_n\) and \(K_n-I\)
cites work: Even cycle decompositions of complete graphs minus a 1‐factor
cites work: Embedding Partial Steiner Triple Systems
cites work: On the Alspach conjecture
cites work: Packing circuits into \(K_N\).
cites work: Decompositions of complete graphs into triangles and Hamilton cycles
cites work: List decomposition of graphs.
cites work: On Alspach's conjecture
cites work: Q4262238
cites work: Cycle decompositions. III: Complete graphs and fixed length cycles.
DOI: 10.1016/J.JCTB.2004.06.002
Recommended article: \((4, 5)\)-cycle systems of complete multipartite graphs
Recommended article: Decomposition of the complete graph plus a 1‐factor into cycles of equal length
Recommended article: Decomposition of complete bipartite graphs into cycles of distinct even lengths
Recommended article: On decomposing \(K_n -I\) into cycles of a fixed odd length
Recommended article: Cycle decompositions of \(K_n\) and \(K_n-I\)
Recommended article: Decomposing complete equipartite graphs into short even cycles
Recommended article: Cycle decompositions. III: Complete graphs and fixed length cycles.
Recommended article: Even cycle decompositions of complete graphs minus a 1‐factor
Recommended article: An asymptotic solution to the cycle decomposition problem for complete graphs
Recommended article: The Oberwolfach problem and factors of uniform odd length cycles
description: scientific article; zbMATH DE number 2132708