New results for recognizing convex-QP adverse graphs. (2nd January 2020) - Luz, Carlos J.
ABSTRACT: A 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.