Threshold graph

An example of a 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:

1. Addition of a single isolated vertex to the graph.
2. Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices.

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.

Alternative definitions

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

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. $\epsilon$ is always the first character of the string, and represents the first vertex of the graph. Every subsequent character is either $u$, which denotes the addition of an isolated vertex (or union vertex), or $j$, which denotes the addition of a dominating vertex (or join vertex). For example, the string $\epsilon uuj$ represents a star graph with three leaves, while $\epsilon uj$ represents a path on three vertices. The graph of the figure can be represented as $\epsilon uuujuuj$

Threshold graphs were first introduced by V. Chvatal and P.L. Hammer in their 1977 paper. A full chapter on threshold graphs appears in the book by Martin Charles Golumbic, "Algorithmic Graph Theory and Perfect Graphs". The most complete reference on the topic is the book by Mahadev and Peled, Threshold Graphs and Related Topics.

Threshold graphs are a special case of cograph, split graphs, and trivially perfect graphs. Every graph that is both a cograph and a split graph is a threshold graph. Every graph that is both a trivially perfect graph and the complement graph of a trivially perfect graph is a threshold graph. Threshold graphs are also a special case of interval graphs.

See also

• Series-parallel graph
• Cograph

Bibliography

• Chvátal, Václav; Hammer, Peter L. (1977), "Aggregation of inequalities in integer programming", in Hammer, P. L.; Johnson, E. L.; Korte, B. H.; Nemhauser, G. L. (eds.), Studies in Integer Programming (Proc. Worksh. Bonn 1975), Annals of Discrete Mathematics, vol. 1, Amsterdam: North-Holland, pp. 145–162.

• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, New York: Academic Press. 2nd edition, Annals of Discrete Mathematics, 57, Elsevier, 2004.

• Mahadev, N. V. R.; Peled, Uri N. (1995), Threshold Graphs and Related Topics, Elsevier.