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

[Andrew Weimholt]

I've discovered an error in my program for decomposing K3. The program for
K4 did not have the same error as it required a new method of culling out
duplicates.

The new terms are 1, 1, 1, 19, 2796, ... pending any further corrections.
(Still not in OEIS - but I'm still double checking my results)

Andrew

On Fri, Aug 7, 2015 at 1:36 PM, Andrew Weimholt <andrew.weimholt at gmail.com>
wrote:

> 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/
>>
>
>