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

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

| cite | improve this answer | |
  • $\begingroup$ ? What about honoring $M$ ?! $\endgroup$ – Wlod AA Mar 17 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.