Dilworth number

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