10
$\begingroup$

Q1: For any given finite simple graph G with e edges, does there always exist an $n$ such that the edges of $K_n$ can be partitioned into $\frac{\binom{n}{2}}{e}$ edge-disjoint copies of $G$? If so, can any upper bounds be placed on the minimal required $n$?

Q2: Similarly for digraphs (with twice as many copies)?

Q3: For any loopless multidigraph with maximum edge multiplicity $m$, it seems clear that for some $M>m$, an $M$-complete multidigraph can be exactly partitioned into isomorphic copies of it, even without increasing $n$: if nothing smaller, one can always overlay $n!$ copies of the original multidigraph with each permutation of the vertices. Can this partition always be accomplished with $M=m$, increasing $n$ instead? If not, can tighter bounds be placed on $M$?

Q4: Does allowing loops (and adjusting edge-counts appropriately) fundamentally change any of the above?

Improve this question
$\endgroup$
2
  • $\begingroup$ Dear @Andy Juell: I edited the question slightly; the "more of a 1a+2a+3a, really:" seemed to make no sense (perhaps it meant something like 'Q1,Q2,Q3 again, but for arbitrary multigraphs'). Needless to say, you can re-edit. I also added a condition of 'loopless' in Q3, because otherwise Q4 does not make sense. $\endgroup$
    – Peter Heinig
    Apr 4, 2018 at 7:11
  • $\begingroup$ @PeterHeinig: I had meant to admit that the contents of Q4 might have been presented after each previous question (i.e. Q1a: with loops? , Q2a: with loops?) but imagined this to be less redundant. Sorry for the confusion... $\endgroup$
    – Zomulgustar
    Apr 4, 2018 at 10:45

1 Answer 1

Reset to default
11
$\begingroup$

Q1: yes, this is a theorem by Wilson; see the first paragraph here: https://arxiv.org/abs/1604.07282

Edit: perhaps the book Decomposition of graphs by J. Bosak might be helpful (the preview on google books is quite limited).

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thanks for the lead...may be a while before I can track down the original reference, but indications are that Wilson settled Q2 in the affirmative also. (alastairfarrugia.net/sc-graph/sc-graph-survey.pdf p. 160) $\endgroup$
    – Zomulgustar
    Apr 4, 2018 at 1:39
  • 2
    $\begingroup$ It is perhaps worth pointing out that for a complete answer to Q1 one has to provide at least one $n$ for which $e$ divides $\binom{n}{2}$; obviously, $n=e$ works. Smaller $n$ sometimes work (e.g. if $e=6$, then $n=4$ also ensures that $e$ divides $\binom{n}{2}$). However, since Wilson's theorem involves a 'sufficiently large $n$'-clause, I expect that for most given $G$, one needs a much larger $n$ than $e$, though I haven't found a reference for this. $\endgroup$
    – Peter Heinig
    Apr 4, 2018 at 7:11
  • $\begingroup$ (In my comment at 2018-04-04 07:11:41Z I made a mistake, or rather, I omitted a case: obviously, if $n$ is odd, then $n$ divides $\binom{n}{2}$, but if $n$ is even then it doesn't. So what I should have said is "obviously, if $e$ is odd, then $n=e$ works, while if $e$ is even, then $n=e+1$ works." $\endgroup$
    – Peter Heinig
    Apr 5, 2018 at 12:23
  • $\begingroup$ @PeterHeinig Suppose that $2^k$ is the largest power of 2 that divides $e$ and $k \ge 1$. Then the largest power of 2 that divides $\binom{e+1}{2} = (e+1)\frac{e}{2}$ is $2^{k-1}$, since this is the largest power of 2 that divides $\frac{e}{2}$ and $e+1$ is odd. This mean that $e$ does not divide $\binom{e+1}{2}$, and the same reasoning works for $\binom{e}{2}$. I think you need to use $\binom{2e}{2}$. $\endgroup$
    – David Roberson
    Apr 12, 2018 at 7:45

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.