2
$\begingroup$

Let $T_n$ be the set of all labelled trees with $n$ vertices. For any $T \in T_n$ let $D(T)$ be the 'doubled tree', where each edge of $T$ is replaced by one directed edge in each direction. $D(T)$ is now an Eulerian directed graph with $2(n-1)$ edges and by the B.E.S.T theorem it has $\prod\limits_{i=1}^n (\deg_{D(T)}(v_i)-1)!$ many Euler circuits.

Let $A_n \subset T_n$ be the set of all labelled trees with $n$ vertices, with the property that vertices $v_1$ and $v_2$ have a distance of $2$, i.e. there is no connection between $v_1$ and $v_2$, but there is a $t \in \{3,...,n\}$ such that there are edges $(v_1,v_t)$ and $(v_2,v_t)$.

Question: Is there a simpler formula for the expression $$ \sum\limits_{T \in A_n} \prod\limits_{i=1}^n (\deg_{D(T)}(v_i)-1)! \ , $$ which counts the number of Euler circuits through trees from $A_n$.

If the distance is prescribed as $1$ instead of $2$, then by using the fact that there are ${n-2 \choose d_1-1,...,d_{n}-1}$ many $T \in T_n$ with $d_i = \deg_{T}(v_i) = \deg_{D(T)}(v_i)$ the formula is found to be $2 \frac{(2n-3)!}{n!}$.

Another way of formulating the question would be: For given $d_1,...,d_{n} \in \{1,...,n-1\}^n$ with $d_1+...+d_n = 2n-2$, how many of the ${n-2 \choose d_1-1,...,d_{n}-1}$ many $T \in T_n$ with $d_i = \deg_{T}(v_i) = \deg_{D(T)}(v_i)$ satisfy the condition that $v_1$ and $v_2$ have distance two?

Any help is much apprechiated.

$\endgroup$

1 Answer 1

1
$\begingroup$

Wlog we can use $v_{n-2}$ and $v_{n-1}$ instead of $v_1$ and $v_2$. Then if we let $B_n \subset T_n$ be the set of labelled trees with edges $(v_{n-2}, v_n)$ and $(v_{n-1}, v_n)$, the count for $A_n$ is just $(n-2)$ times the count for $B_n$ (there are $n-2$ choices for $v_t$; swap $v_t$ for $v_n$ if they're different).

The advantage to numbering things this way is that when constructing the Prüfer codes for the trees in $B_n$ the three labelled vertices are the last survivors. The final label in the Prüfer code will be $n$, and the penultimate one (if $n > 3$) will be in $\{n-2, n-1, n\}$. This appears empirically also be to sufficient, although a proof eludes me at present.

If so then the number of trees with given vertex degrees $d_i$ (where each $d_i \ge 1$ and $d_n \ge 2$) having subtree $v_{n-1} - v_n - v_{n-2}$ is a sum of three multinomial coefficients which simplifies to $$\binom{n-2}{d_1-1, \ldots, d_n-1} \frac{(d_n - 1)(d_{n-2} + d_{n-1} + d_n - 4)}{(n-3)(n-2)}$$

Then taking the alternative formulation

For given $d_1,...,d_{n} \in \{1,...,n-1\}^n$ with $d_1+...+d_n = 2n-2$, how many of the ${n-2 \choose d_1-1,...,d_{n}-1}$ many $T \in T_n$ with $d_i = \deg_{T}(v_i) = \deg_{D(T)}(v_i)$ satisfy the condition that $v_1$ and $v_2$ have distance two?

the answer is given by relabelling to put the special vertices at $v_1$, $v_2$ and summing over all possible intermediate vertices. $$\sum_{i=3}^n [d_i \ge 2] \binom{n-2}{d_1-1, \ldots, d_n-1} \frac{(d_i - 1)(d_1 + d_2 + d_i - 4)}{(n-3)(n-2)}$$ simplifies to $$\frac{1}{(n-3)(n-2)} \binom{n-2}{d_1-1, \ldots, d_n-1} \left((n - d_1 - d_2)(d_1 + d_2 - 5) - (n-2) + \sum_{i=3}^n d_i^2 \right)$$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.