Threshold graph
From Encyclopedia of Mathematics
2020 Mathematics Subject Classification: Primary: 05C [MSN][ZBL]
A finite unoriented graph 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=53966
Threshold graph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Threshold_graph&oldid=53966