Return to Revisions

Let $T^n$ be a path with $2n$ edges rooted at its middle vertex. If I understand your question correctly, then $S$ has Property $m$ if and only if it does not contain $T^{m+1}$ as a rooted subtree. Property $m$ can also be described globally, rather than forbidding local structure. For example, $S$ has Property 1, if and only if it is a Caterpillar_tree, where one end of the central path is the root $v_0$. Property $m$ can also be defined via generalizations of Caterpillar trees. Namely, say that a tree is an $m$-caterpillar if all vertices are within distance $m$ of a central path. Then $S$ has property $m$ if and only if $S$ is an $m$-caterpillar, where one end of the central path is the root $v_0$.