Decompositions of complete multigraphs into stars of varying sizes

DOI10.1016/J.JCTB.2020.05.001zbMATH Open1448.05160arXiv1807.10738OpenAlexW2884040980MaRDI QIDQ2200917FDOQ2200917

Authors: Rosalind A. Cameron, Daniel Horsley 

Publication date: 24 September 2020

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: In 1979 Tarsi showed that an edge decomposition of a complete multigraph into stars of size $m$ exists whenever some obvious necessary conditions hold. In 1992 Lonc gave necessary and sufficient conditions for the existence of an edge decomposition of a (simple) complete graph into stars of sizes $m_1,ldots,m_t$. We show that the general problem of when a complete multigraph admits a decomposition into stars of sizes $m_1,ldots,m_t$ is $mathsfNP$-complete, but that it becomes tractable if we place a strong enough upper bound on $max(m_1,ldots,m_t)$. We determine the upper bound at which this transition occurs. Along the way we also give a characterisation of when an arbitrary multigraph can be decomposed into stars of sizes $m_1,ldots,m_t$ with specified centres, and a generalisation of Landau's theorem on tournaments.

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

Recommendations

• Multigraph decomposition into stars and into multistars
• scientific article; zbMATH DE number 969114
• On the decompositions of complete graphs into cycles and stars on the same number of edges
• scientific article; zbMATH DE number 2192170
• Directed star decompositions of the complete directed graph

zbMATH Keywords

NP-completenesstournamentstaredge decompositioncomplete multigraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Combinatorial matrix classes
• Title not available (Why is that?)
• The difference between consecutive primes. II
• Title not available (Why is that?)
• Packing paths in complete graphs
• Decomposition of complete multigraphs into stars
• On claw-decomposition of complete graphs and complete bigraphs
• Maximum packings of \(K_n\) with \(k\)-stars
• On the decomposition of a graph into stars
• Star decompositions of cubes
• Tournaments associated with multigraphs and a theorem of Hakimi
• Title not available (Why is that?)
• Decompositions of complete multigraphs into cycles of varying lengths
• The real truth about star designs
• Multigraph decomposition into stars and into multistars
• Partitions, packings and coverings by families with nonempty intersections
• Title not available (Why is that?)

Cited In (7)

• Star number and star arboricity of a complete multigraph
• Directed star decompositions of the complete directed graph
• Multigraph decomposition into stars and into multistars
• Determination of the star valency of a graph
• Directed star decompositions of directed multigraphs
• Smaller embeddings of partial \(k\)-star decompositions
• Title not available (Why is that?)

This page was built for publication: Decompositions of complete multigraphs into stars of varying sizes

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