Multigraph decomposition into stars and into multistars

DOI10.1016/J.DISC.2005.03.012MaRDI QIDQ2487986zbMATH OpenOpenAlexFDO

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

decision problemNP-completeness

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

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

• 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
• 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?)
• 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)

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

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)