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
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
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A note on the decomposition of graphs into isomorphic matchings
- Title not available (Why is that?)
- Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
- The NP-Completeness of Some Edge-Partition Problems
- Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
- NP-completeness of graph decomposition problems
- Perfect path double covers of graphs
- On some multigraph decomposition problems and their computational complexity
Cited In (15)
- Title not available (Why is that?)
- 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
- Multigraph decomposition into multigraphs with two underlying edges
- Packing plane spanning graphs with short edges in complete geometric graphs
- The real truth about star designs
- Directed star decompositions of the complete directed graph
- Determination of the star valency of a graph
- Cyclic decompositions of \(\lambda K_n\) into LWO graphs
- Problems and invariants connected with bicliques and multicliques of graphs
- On cyclic near-Hamiltonian cycle system of the complete multigraph
- Title not available (Why is that?)
- 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
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)
