Difference between revisions of "Threshold graph"
From Encyclopedia of Mathematics
(characterisations, cite Golumbic & Trenk (2004)) |
(→References: isbn) |
||
| (2 intermediate revisions by one other user not shown) | |||
| Line 2: | Line 2: | ||
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$. | 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 [[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 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 graph]]s of [[threshold order]]s. | * They are the [[comparability graph]]s of [[threshold order]]s. | ||
| Line 13: | Line 13: | ||
==References== | ==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}} | + | * 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}} | + | * 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}} |
{{TEX|done}} | {{TEX|done}} | ||
Latest revision as of 18:14, 1 June 2023
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=37435
Threshold graph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Threshold_graph&oldid=37435