Difference between revisions of "Threshold graph"
From Encyclopedia of Mathematics
(Redirected page to Dilworth number) |
(Start article: Threshold graph) |
||
| Line 1: | Line 1: | ||
| − | + | {{MSC|05C}} | |
| + | |||
| + | A graph with [[Dilworth number]] $1$: for any two vertices $x,y$, one of the neighbourhoods $N(x)$, $N(y)$ contains the other. Such graphs are characterised by having 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. | ||
| + | |||
| + | There is a polynomial time algorithm for computing the Dilworth number of a finite 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}} | ||
| + | |||
| + | {{TEX|done}} | ||
Revision as of 22:22, 9 January 2016
2020 Mathematics Subject Classification: Primary: 05C [MSN][ZBL]
A graph with Dilworth number $1$: for any two vertices $x,y$, one of the neighbourhoods $N(x)$, $N(y)$ contains the other. Such graphs are characterised by having 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.
There is a polynomial time algorithm for computing the Dilworth number of a finite 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
How to Cite This Entry:
Threshold graph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Threshold_graph&oldid=37332
Threshold graph. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Threshold_graph&oldid=37332