Multigraph decomposition into stars and into multistars

DOI10.1016/J.DISC.2005.03.012zbMATH Open1066.05116OpenAlexW1970065947MaRDI QIDQ2487986FDOQ2487986

Authors Miri Priesler, Michael Tarsi

Publication date 17 August 2005

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2005.03.012

zbMATH Keywords

NP-completenessdecision problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) 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)

Recommendations

• Decompositions of complete multigraphs into stars of varying sizes
• Decomposition of the complete bipartite multigraph into cycles and stars
• scientific article; zbMATH DE number 2192170
• Decomposition of balanced complete bipartite multigraphs into multistars
• Edge decompositions into two kinds of graphs

Cites work

• scientific article; zbMATH DE number 47528 (Why is no real title available?)
• scientific article; zbMATH DE number 3503285 (Why is no real title available?)
• scientific article; zbMATH DE number 3517174 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A note on the decomposition of graphs into isomorphic matchings
• Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• NP-completeness of graph decomposition problems
• On some multigraph decomposition problems and their computational complexity
• Perfect path double covers of graphs
• The NP-Completeness of Some Edge-Partition Problems

Cited in

(15)

• Cyclic decompositions of \(\lambda K_n\) into LWO graphs
• Decompositions of complete multigraphs into stars of varying sizes
• Colorful edge decomposition of graphs: some polynomial cases
• On decomposing regular graphs into isomorphic double-stars
• Multigraph decomposition into multigraphs with two underlying edges
• Directed star decompositions of the complete directed graph
• scientific article; zbMATH DE number 2192170 (Why is no real title available?)
• Determination of the star valency of a graph
• Problems and invariants connected with bicliques and multicliques of graphs
• scientific article; zbMATH DE number 5237247 (Why is no real title available?)
• The real truth about star designs
• Packing plane spanning graphs with short edges in complete geometric graphs
• On the star decomposition of a graph: hardness results and approximation for the max-min optimization problem
• Decomposition of balanced complete bipartite multigraphs into multistars
• On cyclic near-Hamiltonian cycle system of the complete multigraph

This page was built for publication: Multigraph decomposition into stars and into multistars

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