Threshold graph
From Encyclopedia of Mathematics
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
2020 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
Threshold graph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Threshold_graph&oldid=37441