# Dilworth number

2010 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

**How to Cite This Entry:**

Dilworth number.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Dilworth_number&oldid=37440