3
$\begingroup$

I'm not a graph theorist, so I apologize if some of the following terminology isn't quite correct.

Let $(T,f,v_0)$ be a complete degree $d$ rooted tree (definition at the end).

Definition. Let $m\ge0$. I'll say that a subtree $S\subset T$ has Property $\boldsymbol m$ if for all vertices $v,w\in S$, the following implication holds: $$ \text{($f^n(v)=f^n(w)$ for some $n\ge0$)} \quad\Longrightarrow\quad f^m(v)=f^m(w). $$

I am interested in knowing:

  1. Is there is a name for a subtree $S\subset T$ (that includes the root $v_0$) having Property $m$?
  2. Is there a standard classification theorem or description for subtrees having Property $m$?

I've partially worked out the answer to (2), but would be happy to simply cite a result in the literature.

For example, if $S$ has Property $0$, then $S$ is what I think is called a branch of the tree.

Definition. A complete degree $d$ rooted tree is a triple $(T,f,v_0)$, where $T$ is a set of vertices, where $v_0\in T$ is the root vertex, where $f:T\setminus\{v_0\}\to T$ is a function that's used to define the directed edges $v\to f(v)$, and where $\#f^{-1}(v)=d$ for every vertex $v\in T$.

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .