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.
a real vertex weight
a real vertex weight
From the definition which uses repeated addition of vertices, one can derive an alternative way of uniquely describing a threshold graph, by means of a string of symbols.
is always the first character of the string, and represents the first vertex of the graph.
represents a star graph with three leaves, while
represents a path on three vertices.
The graph of the figure can be represented as
All these relations can be explained in terms of their characterisation by forbidden induced subgraphs.
C4 is a cycle of four vertices and 2K2 is its complement, that is, two disjoint edges.
This also explains why threshold graphs are closed under taking complements; the P4 is self-complementary, hence if a graph is P4-, C4- and 2K2-free, its complement is as well.
Heggernes & Kratsch (2007) showed that threshold graphs can be recognized in linear time; if a graph is not threshold, an obstruction (one of P4, C4, or 2K2) will be output.
