Premium
Cycle decompositions of complete multigraphs
Author(s) -
Bryant Darryn,
Horsley Daniel,
Maenhaut Barbara,
Smith Benjamin R.
Publication year - 2011
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.20263
Subject(s) - multigraph , combinatorics , mathematics , matching (statistics) , decomposition , discrete mathematics , statistics , graph , ecology , biology
Abstract It is shown that the obvious necessary conditions for the existence of a decomposition of the complete multigraph with n vertices and with λ edges joining each pair of distinct vertices into m ‐cycles, or into m ‐cycles and a perfect matching, are also sufficient. This result follows as an easy consequence of more general results which are obtained on decompositions of complete multigraphs into cycles of varying lengths. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:42‐69, 2010