# Does the family of graphs closed under taking unions and adding dominating vertices have a name?

Let $\mathcal{F}$ be the smallest family of (simple, finite) graphs such that:

1. The empty graph is in $\mathcal{F}$.
2. If $G \in \mathcal{F}$, then $G_{\bullet}$, the graph obtained from $G$ by adding another vertex $v$ connected by an edge to each vertex in $G$, is also in $\mathcal{F}$.
3. If $G,H \in \mathcal{F}$, then $G \cup H \in \mathcal{F}$.

There are natural bijections between $\{G \in \mathcal{F}: \textrm{$G$has$n$vertices}\}$ and the set of rooted (but unlabeled) forests on $n$ vertices and between $\{G \in \mathcal{F}: \textrm{$G$has$n$vertices and is connected}\}$ and the set of rooted (but unlabeled) trees on $n$ vertices.

Does $\mathcal{F}$ have a name? I want to call it something like the set of "generalized threshold graphs" because the rules that define it are close to those of threshold graphs.

## 1 Answer

It appears that you are looking at the family of quasi-threshold graphs. These are the graphs which can be built, starting from $K_1$, by repeatedly taking the disjoint union of two quasi-threshold graphs, or the join of a quasi-threshold graph with a single new vertex.

By the way, if you relax your conditions a bit more, you get the extremely well-studied family of cographs. These are the graphs which can be built, starting from $K_1$, by repeatedly taking the disjoint union or join of two smaller cographs.

• Thank you for this! graphclasses.org is a great resource of which I was previously not aware. Commented Jun 30, 2013 at 20:24