Suppose we are given a rooted tree $T$, and a set of vertices $M$ that separates the root of $T$ from its leaves. In other words, every path from the root of $T$ to a leaf contains a vertex in $M$. Is there a standard term for such a set $M$?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ If you want to keep the arborial metaphor going, perhaps "complete pruning" would be appropriate. $\endgroup$– Ryan BudneyCommented Mar 17, 2020 at 2:14
-
$\begingroup$ If this doesn't have a name yet, I recommend calling it a topping. $\endgroup$– Jesko HüttenhainCommented Mar 17, 2020 at 2:21
-
$\begingroup$ How about "non-leaves"? $\endgroup$– David G. StorkCommented Mar 21, 2020 at 0:25
-
$\begingroup$ @DavidG.Stork The set $M$ may contain leaves. For example, note that if we choose $M$ to be the set of all leaves, then it indeed satisfies the property that every path from the root to a leaf passes through $M$. $\endgroup$– Or MeirCommented Mar 21, 2020 at 13:33
-
$\begingroup$ Define "through." $\endgroup$– David G. StorkCommented Mar 21, 2020 at 13:46
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
1
Call the root node $r$. If you join each leaf node to a dummy sink node $t$, then $M$ would be an $(r,t)$ vertex separator, also known as vertex cut or separating set.
Even without the dummy node, $M$ is an $(r,\ell)$ vertex separator for each leaf node $\ell$.
