# Minimum number of vertices in a tree with pathwidth $h$?

Let $$\mathcal{T}_h$$ be the set of trees with pathwidth $$h$$. What is the minimum,$$|V(T)|$$ over all $$T \in \mathcal{T}_h$$.

I'm guessing this is a fairly easy question. We know that a complete binary tree of height $$2h$$ has pathwidth $$h$$. This gives an upper bound of $$2^{2h}-1$$. Is this tight? Or could there be trees with pathwidth $$h$$ and size polynomial in $$h$$.

• It seems not, here is a possible pointer Commented Apr 18 at 14:27
• Intuitively, I would believe a ternary tree would be better. Commented Apr 18 at 17:17
• @PålGD Good point. A complete ternary tree of height $h$ has pathwidth $h$ (or at least in this paper arxiv.org/pdf/2008.00779.pdf they say it is well known). So this slightly improves the exponent. But is $2^{\Theta(h)}$ the correct answer or is an improvement possible? Commented Apr 19 at 8:22
• @codeR I had a look but couldn't work out the relevance, maybe I'm missing something. Commented Apr 19 at 8:26