Decompositions of complete multigraphs into cycles of varying lengths

Darryn Bryant; Daniel Horsley; Barbara Maenhaut; Benjamin R. Smith

doi:10.1016/j.jctb.2017.09.005

Decompositions of complete multigraphs into cycles of varying lengths

Darryn Bryant, Daniel Horsley, Barbara Maenhaut, Benjamin R. Smith

School of Mathematics

Research output: Contribution to journal › Article › Research › peer-review

17 Citations (Scopus)

Abstract

We establish necessary and sufficient conditions for the existence of a decomposition of a complete multigraph into edge-disjoint cycles of specified lengths, or into edge-disjoint cycles of specified lengths and a perfect matching.

Original language	English
Pages (from-to)	79–106
Number of pages	28
Journal	Journal of Combinatorial Theory, Series B
Volume	129
DOIs	https://doi.org/10.1016/j.jctb.2017.09.005
Publication status	Published - Mar 2018

Keywords

Complete multigraph
Cycle decomposition
Edge decomposition

Access to Document

10.1016/j.jctb.2017.09.005

Cite this

@article{c0a7098c3bce4517814a6d88c707b802,

title = "Decompositions of complete multigraphs into cycles of varying lengths",

abstract = "We establish necessary and sufficient conditions for the existence of a decomposition of a complete multigraph into edge-disjoint cycles of specified lengths, or into edge-disjoint cycles of specified lengths and a perfect matching.",

keywords = "Complete multigraph, Cycle decomposition, Edge decomposition",

author = "Darryn Bryant and Daniel Horsley and Barbara Maenhaut and Smith, {Benjamin R.}",

year = "2018",

month = mar,

doi = "10.1016/j.jctb.2017.09.005",

language = "English",

volume = "129",

pages = "79–106",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press",

}

TY - JOUR

T1 - Decompositions of complete multigraphs into cycles of varying lengths

AU - Bryant, Darryn

AU - Horsley, Daniel

AU - Maenhaut, Barbara

AU - Smith, Benjamin R.

PY - 2018/3

Y1 - 2018/3

N2 - We establish necessary and sufficient conditions for the existence of a decomposition of a complete multigraph into edge-disjoint cycles of specified lengths, or into edge-disjoint cycles of specified lengths and a perfect matching.

AB - We establish necessary and sufficient conditions for the existence of a decomposition of a complete multigraph into edge-disjoint cycles of specified lengths, or into edge-disjoint cycles of specified lengths and a perfect matching.

KW - Complete multigraph

KW - Cycle decomposition

KW - Edge decomposition

UR - http://www.scopus.com/inward/record.url?scp=85030330620&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2017.09.005

DO - 10.1016/j.jctb.2017.09.005

M3 - Article

AN - SCOPUS:85030330620

VL - 129

SP - 79

EP - 106

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

SN - 0095-8956

ER -

Decompositions of complete multigraphs into cycles of varying lengths

Abstract

Keywords

Access to Document

Other files and links

Matchings in Combinatorial Structures

Partitioning and ordering Steiner triple systems

A new approach to compressed sensing

Cite this

Decompositions of complete multigraphs into cycles of varying lengths

Abstract

Keywords

Access to Document

Other files and links

Projects

Matchings in Combinatorial Structures

Partitioning and ordering Steiner triple systems

A new approach to compressed sensing

Cite this