Cycle systems in the complete bipartite graph minus a one-factor
type: Item
instance of: scholarly article
title: Cycle systems in the complete bipartite graph minus a one-factor
zbMATH Open document ID: 1049.05020
author: Marisa Debowsky
author: J. H. Dinitz
author: Dan S. Archdeacon
author: Heather Jordon
published in: Discrete Mathematics
publication date: 2004-08-20T00:00:00Z
review text: In this paper the edge decomposition of \(K_{n,n}- I\) (the complete bipartite graph from which a 1-factor is removed) into a family of \(m\)-cycles is investigated. Necessary conditions for the existence of such a decomposition are that \(m\geq 4\) even, \(n\geq 3\) odd, \(m< 2n\) and \(m| n(n -1)\). The authors prove that these necessary conditions are sufficient if either \( m\equiv 2\text{\,mod\,}4\) and \(m\leq 2n\) or \(m\equiv 0\text{\,mod\,}4\) and \(m\leq n\) (leaving open the case when \(m\equiv 0\text{\,mod\,} 4\) and \(n< m< 2n\)). The proof cleverly uses the concept of Cayley graphs and difference constructions.
Mathematics Subject Classification ID: 05B30
zbMATH DE Number: 2093765
zbMATH Keywords: decomposition
zbMATH Keywords: cycles
zbMATH Keywords: Cayley graphs
zbMATH Keywords: complete bipartite graph
reviewed by: Jorge Luis Ramírez Alfonsín
MaRDI profile type: Publication
full work available at URL: j.disc.2003.11.021
OpenAlex ID: W1994453579
cites work: Cycle decompositions of \(K_n\) and \(K_n-I\)
cites work: Q4222083
cites work: Decompositions of complete multipartite graphs into cycles of even length
cites work: Hamiltonian decompositions of complete regular s-partite graphs
cites work: On decomposition of r-partite graphs into edge-disjoint Hamilton circuits
cites work: Q4842729
cites work: Q4876946
cites work: Cycle decompositions. III: Complete graphs and fixed length cycles.
cites work: Decomposition of K//(m,n)(K*//(m,n)) into cycles (circuits) of length 2k
Wikidata QID: Q55891584
DOI: 10.1016/J.DISC.2003.11.021
DBLP publication ID: journals/dm/ArchdeaconDDG04
description: scientific article; zbMATH DE number 2093765