A bound for the Dilworth number (Q809096): Difference between revisions

Finite, undirected graphs \(G=(V,E)\) without loops or multiple edges were considered. For the Dilworth number \(\nabla (G)\) (the cardinality of the maximum size antichains; \textit{R. P. Dilworth} [Ann. Math. Ser. 2, 51, 161-166 (1950; Zbl 0038.020)]) of such a nontrivial simple graph with rank r(G) the inequality \[ \nabla (G)\leq 2r(G)-1 \] was derived. The rank r(G) is the rank of the adjacency matrix of G. In the case of \(\nabla\) odd it holds \[ \nabla (G)\leq 2[r(G)-1]-1. \]