
Threshold graph
Encyclopedia

Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:
- Addition of a single isolated vertex to the graph.
- 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 equivalent definition is the following: a graph is a threshold graph if there are a real number





Another equivalent definition is this: a graph is a threshold graph if there are a real number






The name "threshold graph" comes from the fact that S, or T, is the "threshold" for the property of being an edge, or being independent.
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.






Threshold graphs were first introduced by Chvatal and Hammer in their 1977 paper. A full chapter on threshold graphs appears in the book by Algorithmic Graph Theory and Perfect Graphs by Golumbic. The most complete reference is the book by Mahadev and Peled, Threshold Graphs and Related Topics.
Threshold graphs are a special case of cograph
Cograph
In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union...
s, split graph
Split graph
In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set...
s, 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
Complement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
of a trivially perfect graph is a threshold graph. Threshold graphs are also a special case of interval graph
Interval graph
In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...
s.
External links
- Threshold graphs, Information System on Graph Class Inclusions, Univ. of Rostock.