Continuous characterizations of the maximum clique problem

Given a graph G whose adjacency matrix is A, the Motzkin-Strauss formulation of the Maximum-Clique Problem is the quadratic program max{(T)(x)Ax\x(T)e = 1, x greater than or equal to 0}. It is well known that the global optimum value of this QP is (1 - 1/omega(G)), where omega(G) is the clique number of G. Here, we characterize the following properties pertaining to the above QP: (1) first order optimality, (2) second order optimality, (3) local optimality, (4) strict local optimality. These characterizations reveal interesting underlying discrete structures, and are polynomial time verifiable. A parametrization of the Motzkin-Strauss QP is then introduced and its properties are investigated. Finally, an extension of the Motzkin-Strauss formulation is provided for the weighted clique number of a graph.