Threshold graph

Alternative 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. S=1, w(u)=1 for vertices that were added as dominating vertices and w(u)=0 for all other vertices. For the other direction, given S and w we can construct the same graph by starting with the graph whose only vertex is the vertex with the minimum weight and then examining all remaining vertices in order of non-decreasing weight. Each one is added as a --

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) \le 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.

Decomposition

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 u u j represents a star graph with three leaves, while \epsilon u j represents a path on three vertices. The graph of the figure can be represented as \epsilon uuujuuj

Related classes of graphs and recognition

Threshold graphs are a special case of cographs, split graphs, and trivially perfect graphs. A graph is a threshold graph if and only if it is both a cograph and a split graph. Every graph that is both a trivially perfect graph and the complementary graph of a trivially perfect graph is a threshold graph. Threshold graphs are also a special case of interval graphs. All these relations can be explained in terms of their characterisation by forbidden induced subgraphs. A cograph is a graph with no induced path on four vertices, P4, and a threshold graph is a graph with no induced P4, C4 nor 2K2. 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.

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.

References

• {{citation | editor1-last = Hammer | editor1-first = P. L. | editor2-last = Johnson | editor2-first = E. L. | editor3-last = Korte | editor3-first = B. H. |display-editors = 3 | editor4-last = Nemhauser | editor4-first = G. L.
• {{citation
• {{citation
• {{citation

References

1. (1985-04-01). "Threshold hypergraphs". Discrete Mathematics.