A note on the size of minimal covers

For the class of monotone boolean functions f : {0, 1}(n) -> {0, 1} where all I-certificates have size 2, we prove the tight bound n <= (lambda + 2)(2)/4, where lambda is the size of the largest 0-certificate of f. This result can be translated to graph language as follows: for every graph G = (V, E) the inequality vertical bar V vertical bar <= (lambda + 2)(2)/4 holds, where lambda is the size of the largest minimal vertex cover of G. In addition, there are infinitely many graphs for which this inequality is tight. (c) 2006 Elsevier B.V. All rights reserved.