Difference between revisions of "Dilworth number"
(Start article: Dilworth number) |
(→References: isbn link) |
||
| (2 intermediate revisions by one other user not shown) | |||
| Line 7: | Line 7: | ||
The [[diameter]] of a graph exceeds its Dilworth number by at most 1. | The [[diameter]] of a graph exceeds its Dilworth number by at most 1. | ||
| − | A graph with Dilworth number 1 is a ''threshold graph'', 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$). | + | A graph with Dilworth number 1 is a ''[[threshold graph]]'', 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$). |
There is a polynomial time algorithm for computing the Dilworth number of a finite graph. | There is a polynomial time algorithm for computing the Dilworth number of a finite graph. | ||
==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}} |
{{TEX|done}} | {{TEX|done}} | ||
Latest revision as of 19:14, 14 November 2023
2020 Mathematics Subject Classification: Primary: 05C [MSN][ZBL]
of a graph $G$
A numerical invariant, cf. Graph, numerical characteristics of a. The Dilworth number of the graph $G$ is the maximum number of vertices in a set $D$ for which the neighbourhoods form a Sperner family: for any pair of such vertices $x,y \in D$, each of the neighbourhoods $N(x)$, $N(y)$ has at least one element not contained in the other. It is the width of the set of neighbourhoods partially ordered by inclusion (the vicinal preorder on vertices).
The diameter of a graph exceeds its Dilworth number by at most 1.
A graph with Dilworth number 1 is a threshold graph, 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$).
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
Dilworth number. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Dilworth_number&oldid=37331