<p>Imagine we have a graph, which is 2k-regular, and we want to decompose it into copies of k-stars. Then we could just at first decompose the graph into 2-factors, orient each of the factors and then we can easily decompose the graph into stars: put a center in any vertex and choose k outgoing edges.</p>

<p>I would like to ask about the case of multigraphs (so that we can have now multiple edges between the same pair of vertices, but without loops). It is easy to construct examples, when we cannot find a decomposition. What is known about the complexity of a problem of deciding whether a 2k-regular multigraph has a k-star decomposition?</p>

CC BY-SA 3.0
2013-10-20T03:49:18.827Z
"... As a result of these many ambiguities, use of the term "multigraph" should be deprecated, or at the very least used with extreme caution." [mathworld](http://mathworld.wolfram.com/Multigraph.html)... can you rephrase this in terms of hypergraphs? might lead to more research...
vzn
CC BY-SA 3.0
2013-10-20T08:25:57.203Z
@vzn The question makes it explicit that "multigraph" here means that parallel edges are allowed but loops are not: there is no ambiguity. Frankly, it's ludicrous of Wolfram to assert that we shouldn't say "multigraph", without giving any alternative...
David Richerby
<cc.complexity-theory><graph-theory>
What is the complexity of decomposing 2k-regular multigraphs into k-stars?
gexahedron
# What is the complexity of decomposing 2k-regular multigraphs into k-stars?

(Asked by: username_0 on 2013-10-19)

Imagine we have a graph, which is 2k-regular, and we want to decompose it into copies of k-stars. Then we could just at first decompose the graph into 2-factors, orient each of the factors and then we can easily decompose the graph into stars: put a center in any vertex and choose k outgoing edges.

I would like to ask about the case of multigraphs (so that we can have now multiple edges between the same pair of vertices, but without loops). It is easy to construct examples, when we cannot find a decomposition. What is known about the complexity of a problem of deciding whether a 2k-regular multigraph has a k-star decomposition?

**Tags:** cc.complexity-theory, graph-theory

> **Comments:**
> **username_1**: "... As a result of these many ambiguities, use of the term "multigraph" should be deprecated, or at the very least used with extreme caution." [mathworld](http://mathworld.wolfram.com/Multigraph.html)... can you rephrase this in terms of hypergraphs? might lead to more research...  
> **username_2**: @username_1 The question makes it explicit that "multigraph" here means that parallel edges are allowed but loops are not: there is no ambiguity. Frankly, it's ludicrous of Wolfram to assert that we shouldn't say "multigraph", without giving any alternative...  

---

## 0 answers

