0
$\begingroup$

Given a tree, find the maximum number of vertices $v$ in that tree using the maximum path length $p$ and a maximum degree that applies to all vertices $d$.

Assuming that I drew my test tree correctly, in the case where the path is no longer than $5$, and the vertex degree can be no higher than $3$, then the maximum number of vertices should be $14$. Is this right? I have tried other values for $p$ and $d$ and drawing the trees for them, but don't see the pattern in the data.

I don't know which formula I can use to derive the maximum number of vertices when $p$ and $d$ are unknown. I would like to know what the formula is, if it exists.

$\endgroup$
1
$\begingroup$

The easy case is when $p$ is even. In that case you want $d$ paths coming up from the root (level 0) and each vertex until layer $\frac p2$ has $d-1$ branches upward. This gives $1+d+(d-1)d +(d-1)^2d +\ldots d(d-1)^ {\frac p2-1}=1+d+d\frac{(d-1)^{\frac p2}-1}{d-2}$

If $p$ is odd, you can have one branch of height $\frac {p+1}2$ and all the other branches can have height $\frac {p-1}2$. You should be able to follow the above logic to get the expression in that case.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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