Decomposing complete equipartite multigraphs into cycles of variable lengths: the amalgamation-detachment approach

DOI10.1002/JCD.21419MaRDI QIDQ2804929zbMATH OpenOpenAlexFDO

Authors Mateja Šajna, M. A. Bahmanian

Publication date 6 May 2016

Published in Journal of Combinatorial Designs (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.09644

zbMATH Keywords

amalgamationdetachmentcycle decompositionAlspach's conjecturecomplete equipartite multigraph

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Using the technique of amalgamation-detachment, we show that the complete equipartite multigraph $lambda{K}_{nimesm}$ can be decomposed into cycles of lengths $c_{1}m,dots,c_{k}m$ (plus a 1-factor if the degree is odd) whenever there exists a decomposition of $lambdam{K}_n$ into cycles of lengths $c_1,dots,c_k$ (plus a 1-factor if the degree is odd). In addition, we give sufficient conditions for the existence of some other, related cycle decompositions of the complete equipartite multigraph $lambda{K}_{nimesm}$.

Recommendations

• Decompositions of complete multigraphs into cycles of varying lengths
• Decompositions of complete multipartite graphs into cycles of even length
• Decomposing complete equipartite graphs into cycles of length2p
• scientific article; zbMATH DE number 786153
• Decomposition of a complete bipartite multigraph into arbitrary cycle sizes
• Decomposing complete equipartite graphs into short even cycles
• Cycle decompositions of complete multigraphs
• Cycle decompositions of complete multigraphs
• Decomposition of complete equipartite graphs into paths and cycles of length \(2p\)
• scientific article; zbMATH DE number 5879550

Cites work

• scientific article; zbMATH DE number 1229616 (Why is no real title available?)
• scientific article; zbMATH DE number 1343531 (Why is no real title available?)
• scientific article; zbMATH DE number 5879550 (Why is no real title available?)
• Balanced incomplete block designs and related designs
• Complete equipartite \(3p\)-cycle systems
• Cycle Decompositions of $K_{\lowercase{n,n}}-I$
• Cycle decompositions of complete multigraphs
• Cycle decompositions. V: Complete graphs into cycles of arbitrary lengths
• Cycle systems in the complete bipartite graph minus a one-factor
• Decomposing complete equipartite graphs into cycles of length2p
• Decomposing complete equipartite graphs into odd square-length cycles: number of parts odd
• Decomposing complete equipartite graphs into short even cycles
• Decomposing complete equipartite graphs into short odd cycles
• Decomposing various graphs into short even-length cycles
• Decomposition of K//(m,n)(K*//(m,n)) into cycles (circuits) of length 2k
• Decomposition of \(K_{m, n}\) into 4-cycles and \(2t\)-cycles
• Decomposition of \(K_{m,n}\) into short cycles
• Decompositions of complete multipartite graphs into cycles of even length
• Hamiltonian decompositions of complete graphs
• Hamiltonian decompositions of complete regular s-partite graphs
• On decomposition of r-partite graphs into edge-disjoint Hamilton circuits
• Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts
• Path and cycle decompositions of complete equipartite graphs: Four parts
• \(C_{p}\)-decompositions of some regular graphs

Cited in

(10)

• Decompositions of complete equipartite graphs into cycles of lengths 3 and 6
• Decomposing \(K_{u + w} - K_u\) into cycles of prescribed lengths
• \(p^2\)-cycle decompositions of the tensor product of complete graphs
• Resolvable cycle decompositions of complete multigraphs and complete equipartite multigraphs via layering and detachment
• Cyclic cycle systems of the complete multipartite graph
• Decompositions of complete tripartite graphs into cycles of lengths 3 and 6
• Decompositions of some classes of dense graphs into cycles of lengths 4 and 8
• Decomposition of complete equipartite graphs into paths and cycles of length \(2p\)
• Decomposition of the tensor product of complete graphs into cycles of lengths 3 and 6
• Decomposition of a complete bipartite multigraph into arbitrary cycle sizes

This page was built for publication: Decomposing complete equipartite multigraphs into cycles of variable lengths: the amalgamation-detachment approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2804929)