4
$\begingroup$

Let $G$ be a multigraph with maximum edge multiplicity $t$ and minimum edge multiplicity $1$ (so that there is at least one 'ordinary' edge).

Is there some simple graph $H$ such that the $t$-fold multigraph $H^{(t)}$ edge-decomposes into copies of $G$?

I believe that Wilson's theory (under certain hypotheses) gives a solution when $H$ is a certain very large complete graph. For instance, see Draganova, Mutoh, Wilson (2008). Heavy machinery gets used there.

Is there a more direct argument if I don't care what $H$ is or how large it is?

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $G$ be an arbitrary graph with $4$ edges, with multiplicities $1, 2, 2, 3$. Then in any decomposition of an $H^{(3)}$ every triple edge would have to split as $\{3\}$ or $\{1, 2\}$. In particular, there would be equal numbers of $G$-edges of multiplicities $1$ and $2$, which isn't the case for any union of copies of $G$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.