A characterization of the weighted Lovasz number based on convex quadratic programming

作者：Luz Carlos J^*

来源：Optimization Letters, 2016, 10(1): 19-31.

DOI：10.1007/s11590-015-0911-6

• Weighted Lovasz number
• Maximum weight stable set
• Combinatorial optimization
• Graph theory
• Quadratic programming

Luz and Schrijver (SIAM J Discrete Math 19(2):382-387, 2005) introduced a characterization of the Lovasz number based on convex quadratic programming. This characterization is now extended to the weighted version of that number. In consequence, a class of graphs for which the weighted Lovasz number coincides with the weighted stability number is characterized. Several examples of graphs of this class are presented.

• 出版日期2016-1