Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Threshold graph

Graph formed by adding isolated or universal vertices

Wikipedia contributorsAdapted for Fathomly · View authors
2 min read
Source updated April 14, 2026
Image credit is listed at the end of this article.

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.

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.

01Alternative definitions

An 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, uv is an edge if and only if w(u)+w(v)>S.

Another equivalent definition is this: a graph is a threshold graph if there are a real number T and for each vertex v a real vertex weight a(v) such that for any vertex set X\subseteq V, X is independent if and only if \sum _{v\in X}a(v)\leq T.

The name "threshold graph" comes from these definitions: S is the "threshold" for the property of being an edge, or equivalently T is the threshold for being independent.

Threshold graphs also have a forbidden graph characterization: A graph is a threshold graph if and only if it no four of its vertices form an induced subgraph that is a three-edge path graph, a four-edge cycle graph, or a two-edge matching.

02Decomposition

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

Watch videos about Threshold graphExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Threshold graph”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Indifference graph

In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. An indifference graph is also the intersection graph of a set of unit intervals, or of properly nested intervals.

Series-parallel graph

In graph theory, series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.