Decompositions of complete multigraphs into stars of varying sizes

DOI10.1016/J.JCTB.2020.05.001MaRDI QIDQ2200917zbMATH OpenOpenAlexFDO

Authors Rosalind A. Cameron, Daniel Horsley

Publication date 24 September 2020

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

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

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)

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.

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

Cites work

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

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
• scientific article; zbMATH DE number 2192170 (Why is no real title available?)

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)