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$.

Improve this question
$\endgroup$
8
  • $\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
    Commented Sep 6, 2017 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
    Commented Sep 6, 2017 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
    Commented Sep 6, 2017 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
    Commented Sep 6, 2017 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
    Commented Sep 8, 2017 at 20:59

0

Reset to default

You must log in to answer this question.