12
$\begingroup$

I wonder what is known on the following:

1) What is the number $T_k(n)$ of $k$-tuples of (pairwise) edge-disjoint trees $(T_1,T_2,\dots, T_k)$ with $n$ labelled vertices?

2) (harder, it seems) What is the number $S_k(n)$ of subgraphs with $n$ labelled vertices which are union of $k$ (pairwise) edge-disjoint trees?

3) What is the number $R_k(n)$ of $k$-tuples of (pairwise) edge-disjoint trees $(T_1,T_2,\dots, T_k)$ on the set of vertices $[n]={1,2,\dots,n}$ such that $T_i$ is a tree with $n-i$ edges?

4) (Like 2) What is the number $U_k(n)$ of subgraphs with $n$ labelled vertices which are union of $k$ (pairwise) edge-disjoint trees $(T_1,T_2,\dots, T_k)$ on the set of vertices $[n]={1,2,\dots,n}$ such that $T_i$ is a tree with $n-i$ edges?

(Added Sept 7, 2017): 5) What is the number $F_k(n)$ of $k$-tuples of (pairwise) edge-disjoint forests $(F_1,F_2,\dots, F_k)$ on the set of vertices $[n]={1,2,\dots,n}$ such that $F_i$ is a spanning forest with $n-i$ edges?

6) Variant on 5): Rooted forests rather than forests. (Call the number $G_k(n)$.)

Of course, Cayley's formula for the number of trees on $n$ labelled vertices gives that $T_1(n)=S_1(n)=R_1(n)=U_1(n)=F_1(n)=G_1(n)=n^{n-2}$ but I wonder if something is known even for $k=2$.

$\endgroup$
  • $\begingroup$ Does each tree have to be on the $n$ vertices, or it can be a tree on a subset of those vertices? $\endgroup$ – Max Alekseyev Sep 6 '17 at 0:02
  • $\begingroup$ On p81 of Moon, Counting Labelled Trees, there is a formula for the number of pairs of trees on $n$ vertices with exactly $m$ edges in common, but I didn't manage to get sensible numbers out of it. Perhaps there is a typo. ADDED: cambridge.org/core/journals/mathematika/article/… $\endgroup$ – Brendan McKay Sep 6 '17 at 2:07
  • $\begingroup$ @BrendanMcKay: The formula looks reasonable to me. For $n=1,2,\dots$, I got the number of edge-disjoint ordered pairs of tress on the same $n$ vertices equal: 1, 0, 0, 12, 1140, 147240, 27351240, 7080803520, 2459711381904, 1109036355638400, ... $\endgroup$ – Max Alekseyev Sep 6 '17 at 4:40
  • 1
    $\begingroup$ In the case of Q2 for two spanning trees, there is a thm of Nash-Williams that a graph on $n$ vertices is the union of two spanning trees iff it has $2n-2$ edges and each subset $E'$ of the edge set has $|E'| \le 2k-2$ where $k$ is the number of endpoints of $E'$. I doubt that helps to count them. $\endgroup$ – Brendan McKay Sep 6 '17 at 8:35
  • 1
    $\begingroup$ @BrendanMcKay: It seems that the theorem by Nash-Williams covers the case of $k$ trees as well, at least that's what's said in Harari's book. $\endgroup$ – Ilya Bogdanov Sep 8 '17 at 20:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.