New results for recognizing convex-QP adverse graphs

ABSTRACTA graph G with convex-QP stability number (or simply a convex-QP graph) is a graph for which the stability number is equal to the optimal value of a convex quadratic programme, say P(G). The problem of recognizing in polynomial time whether or not a given graph is a convex-QP graph has resisted to be completely solved. In this paper, some progress recently made for trying to settle this open question is reported. Namely, if G is a graph such that the optimal solutions of P(G) are critical points of the objective function, some new necessary and sufficient conditions for G to be a convex-QP graph are proved. The practical value of two of these results is also exemplified.