-

 

 

 




Optimization Online





 

On graphs with stability number equal to the optimal value of a convex quadratic program

Domingos M. Cardoso (dcardoso***at***mat.ua.pt)

Abstract: 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.

Keywords: Stable sets (05C69); Programming involving graphs (90C35)

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: Matemática Contemporânea (Sociedade Brasileira de Matemática), 25 (2003): 9-24.

Download:

Entry Submitted: 07/08/2002
Entry Accepted: 07/09/2002
Entry Last Modified: 11/03/2003

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society