[seqfan] Re: Number of ways to decompose K_2n into n spanning trees (unlabeled nodes)

[Andrew Weimholt]

I guess there is some ambiguity as to what is meant by a decomposition of a
graph.

I am using the term to mean a partition of the graph's edges, so that no
two subgraphs share any of the edges (though they do share the nodes), and
the union of the subgraphs is the original graph (in this case the complete
graph).
The trees must be spanning trees of the complete graph, so each tree has 2n
nodes and 2n-1 edges. With n trees, we have (n)(2n-1) edges, which cover
all the edges of the complete graph of 2n nodes.

You can also think of this as the number of ways to color the edges of K_2n
with n colors, such that each color is a spanning tree of K_2n.

Andrew




On Fri, Aug 7, 2015 at 1:28 PM, Giovanni Resta <g.resta at iit.cnr.it> wrote:

>  07/08/2015 21:27, Andrew Weimholt:
>
>> So far, I have
>>
>> 1 way to decompose k0 (null graph) into 0 trees.
>> 1 way to decompose k2 into 1 tree.
>> 1 way to decompose k4 into 2 trees.
>>
> I think I'm  missing something.
>
> K_4 has 4 nodes. I always make confusion between labeled and unlabeled
> graphs, but here I expected at least two decompositions, instead of one.
> Namely, a decomposition into two trees of 2 nodes each and one
> decomposition into a tree of 3 nodes and a tree of 1 node.
> Could you explain better your sequence ?
> Giovanni
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>