Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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