3
$\begingroup$

Which spanning forests can we partition the complete graph $K_n$ into? I am primarily interested in partitions into one fixed isomorphism class of forest. I'm also assuming whatever divisibility conditions we need on $n$ (in particular if $F$ is the forest, the sum of its degrees divides $n(n-1)$). The two examples I know of for $n$ even are perfect matchings and hamiltonian paths. Can we classify the forests that will work?
(edit) Clarification: By a partition of $K_n$ I am talking about a partition of the edge set of $K_n$, all $n \choose 2$ edges, into copies of the forest $F$.

$\endgroup$
1
$\begingroup$

The problem you pose seems to be wide open, as indicated in a number of recent publications devoted to it. Even in a special case when a forest is a tree not as much is known. There is a recent conjecture by Haler and Wang: $k$ edge disjoint copies of a tree $T$ on $n$ vertices can be placed in the complete graph if and only if every vertex of $T$ has degree less than $n-k$, see their paper (checking it for $k=4$) for precise formulation.

When $F$ is an arbitrary forest, less seems to be known. There are interesting results concerning arbitrary graphs $F$, as well as those on many other graph classes, though.

$\endgroup$
  • $\begingroup$ Thanks, though I think this is a more general (and probably harder) problem than I am asking. I am not looking for packing a constant, $k$, copies into $E(K_n)$ but rather using up all of $E(K_n)$. So I guess in that language I want forests, $F$, which are $|E(K_n)|/|E(F)|$ placeable. $\endgroup$ – CoffeeCat Sep 1 '14 at 23:25
  • $\begingroup$ @CoffeeCat I agree that your problem is not that general. However, a special case of it still seems to be a known open problem, for which I tried to give a reference. $\endgroup$ – user2097 Sep 1 '14 at 23:36

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.