Threshold graph

In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:

For example, the graph of the figure is a threshold graph. It can be constructed by beginning with a single-vertex graph (vertex 1), and then adding black vertices as isolated vertices and red vertices as dominating vertices, in the order in which they are numbered.

Threshold graphs were first introduced by Chvátal & Hammer (1977). A chapter on threshold graphs appears in Golumbic (1980), and the book Mahadev & Peled (1995) is devoted to them.

An equivalent definition is the following: a graph is a threshold graph if there are a real number ${\displaystyle S}$ and for each vertex ${\displaystyle v}$ a real vertex weight ${\displaystyle w(v)}$ such that for any two vertices ${\displaystyle v,u}$, ${\displaystyle uv}$ is an edge if and only if ${\displaystyle w(u)+w(v)>S}$.

...
Wikipedia