Since the Motzkin-Straus result on the clique number of graphs, published in 1965, where they show that the size of the largest clique in a graph can be obtained by solving a quadratic programming problem, several results on the continuous approach to the determination of the clique number of a graph or, equivalently, to the determination of the stability number of its complement, have been published. In this paper, a Motzkin-Straus-like approach to the stability number of graphs is presented and extended to the study of graphs for which the stability number is equal to the optimal value of a convex quadratic programming problem (called graphs with convex-$QP$ stability number) as well as the determination of convex quadratic lower and upper bounds on the stability number of arbitrary graphs. In the presence of adverse conditions, it is proved that the recognition of graphs with convex-$QP$ stability number is equivalent to the recognition of graphs with a particular combinatorial structure (called regular-stable graphs). Additionally, for particular types, as is the case of line graphs of forests or threshold graphs, the polynomial-time recognition of graphs with convex-$QP$ stability number is introduced.
Citation
Matemática Contemporânea (Sociedade Brasileira de Matemática), 25 (2003): 9-24.