1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ If you want to keep the arborial metaphor going, perhaps "complete pruning" would be appropriate. $\endgroup$ Mar 17, 2020 at 2:14
  • $\begingroup$ If this doesn't have a name yet, I recommend calling it a topping. $\endgroup$ Mar 17, 2020 at 2:21
  • $\begingroup$ How about "non-leaves"? $\endgroup$ 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 Meir
    Mar 21, 2020 at 13:33
  • $\begingroup$ Define "through." $\endgroup$ Mar 21, 2020 at 13:46

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ ? What about honoring $M$ ?! $\endgroup$
    – Wlod AA
    Mar 17, 2020 at 3:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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