# Threshold graph

From Encyclopedia of Mathematics

2010 Mathematics Subject Classification: *Primary:* 05C [MSN][ZBL]

A finite unoriented graph $G=(V,E)$ with a weight function $w : V \rightarrow \mathbf{R}$ and a threshold value $T$ such that a set $S$ of vertices is independent (has no edges) if and only if $\sum_{v \in S} w(v) < T$. Each of the following properties characterises threshold graphs:

- They have Dilworth number $1$: for any two vertices $x,y$, one of the neighbourhoods $N(x)$, $N(y)$ contains the other.
- They have no induced subgraph of the form $K_{2,2}$ (complete bipartite on $2+2$ points) , $C_4$ (cycle of length $4$) or $P_4$ (path of length $4$).
- They are the comparability graphs of threshold orders.

A graph $G$ is a threshold graph if and only if the graph complement $\bar G$ is a threshold graph.

There is a polynomial time algorithm for computing the Dilworth number of a finite graph and so for recognising a threshold graph.

## References

- Andreas Brandstädt, Van Bang Le; Jeremy P. Spinrad, "Graph classes: a survey". SIAM Monographs on Discrete Mathematics and Applications
**3**. Society for Industrial and Applied Mathematics (1999) ISBN 978-0-898714-32-6 Zbl 0919.05001 - Golumbic, Martin Charles; Trenk, Ann N.
*Tolerance graphs*Cambridge Studies in Advanced Mathematics**89**Cambridge University Press (2004) ISBN 0-521-82758-2 Zbl 1091.05001

**How to Cite This Entry:**

Threshold graph.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Threshold_graph&oldid=37441