Premium
Resolvable cycle decompositions of complete multigraphs and complete equipartite multigraphs via layering and detachment
Author(s) -
Bahmanian Amin,
Šajna Mateja
Publication year - 2021
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.21792
Subject(s) - mathematics , combinatorics , matching (statistics) , vertex (graph theory) , variable (mathematics) , discrete mathematics , graph , mathematical analysis , statistics
Abstract We construct new resolvable decompositions of complete multigraphs and complete equipartite multigraphs into cycles of variable lengths (and a perfect matching if the vertex degrees are odd). We develop two techniques: layering , which allows us to obtain 2‐factorizations of complete multigraphs from existing 2‐factorizations of complete graphs, and detachment , which allows us to construct resolvable cycle decompositions of complete equipartite multigraphs from existing resolvable cycle decompositions of complete multigraphs. These techniques are applied to obtain new 2‐factorizations of a specified type for both complete multigraphs and complete equipartite multigraphs, with the emphasis on new solutions to the Oberwolfach Problem and the Hamilton–Waterloo Problem. In addition, we show existence of some thickly resolvable cycle decompositions.