What is the name of sets of nodes of a tree that cover/span/cut the entire width of the tree?

Question

What are the following sets called?

They may be constructed by repeating the following recipe.

1. Choose a parent node
2. Remove the parent node's descendents
3. Repeat as desired while parent nodes remain.

Here is a tree in graphviz dot.

digraph G {a->b;
    a->c;
    a->d;
    b->e;
    b->f;
    e->g;
    e->h;
    c->i;
    c->j;
}

Here are four of many possible sets of nodes that cover the full width of the tree.

g,h,g,i,j,d graph1

a graph2

b,c,d graph3

b,i,j,d graph4

My best guess is covering set, spanning set, cutting set?

David

Answer 1

If I understand correctly, these are the maximal antichains: sets of nodes in which no two are comparable, but such that any node outside the set is comparable with some node in the set. These make sense for arbitrary partial orderings, not just trees specifically.

(As an aside, note that it's easy to see that maximal antichains exist in every finite partial ordering; for infinite partial orderings, we need the axiom of choice.)