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

DOI10.1002/JCD.21419zbMATH Open1338.05208arXiv1909.09644OpenAlexW3125459157MaRDI QIDQ2804929FDOQ2804929

Authors: Mateja Šajna, M. A. Bahmanian 

Publication date: 6 May 2016

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

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}$.

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

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

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)

Cites Work

• Decomposition of K//(m,n)(K*//(m,n)) into cycles (circuits) of length 2k
• Cycle decompositions V: Complete graphs into cycles of arbitrary lengths
• Cycle decompositions of complete multigraphs
• Balanced incomplete block designs and related designs
• Hamiltonian decompositions of complete regular s-partite graphs
• On decomposition of r-partite graphs into edge-disjoint Hamilton circuits
• Hamiltonian decompositions of complete graphs
• Cycle Decompositions of $K_{\lowercase{n,n}}-I$
• Decomposition of \(K_{m,n}\) into short cycles
• Decomposition of \(K_{m, n}\) into 4-cycles and \(2t\)-cycles
• Path and cycle decompositions of complete equipartite graphs: Four parts
• Decomposing complete equipartite graphs into short odd cycles
• Decompositions of complete multipartite graphs into cycles of even length
• \(C_{p}\)-decompositions of some regular graphs
• 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 cycles of length2p
• Title not available (Why is that?)
• Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts
• Complete equipartite \(3p\)-cycle systems
• Decomposing various graphs into short even-length cycles
• Title not available (Why is that?)
• Title not available (Why is that?)
• Cycle systems in the complete bipartite graph minus a one-factor

Cited In (10)

• Decomposing \(K_{u + w} - K_u\) into cycles of prescribed lengths
• Resolvable cycle decompositions of complete multigraphs and complete equipartite multigraphs via layering and detachment
• Title not available (Why is that?)
• Cyclic cycle systems of the complete multipartite graph
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)