A survey on graphs with convex quadratic stability number

DOI10.1080/02331934.2018.1526282zbMATH Open1435.90098arXiv1811.05516OpenAlexW3105185467MaRDI QIDQ5207733FDOQ5207733

Authors: D. M. Cardoso 

Publication date: 13 January 2020

Published in: Optimization (Search for Journal in Brave)

Abstract: A graph with convex quadratic stability number is a graph for which the stability number is determined by solving a convex quadratic program. Since the very beginning, where a convex quadratic programming upper bound on the stability number was introduced, a necessary and sufficient condition for this upper bound be attained was deduced. The recognition of graphs with convex quadratic stability number has been deeply studied with several consequences from continuous and combinatorial point of view. This survey starts with an exposition of some extensions of the classical Motzkin-Straus approach to the determination of the stability number of a graph and its relations with the convex quadratic programming upper bound. The main advances, including several properties and alternative characterizations of graphs with convex quadratic stability number are described as well as the algorithmic strategies developed for their recognition. Open problems and a conjecture for a particular class of graphs, herein called adverse graphs, are presented, pointing out a research line which is a challenge between continuous and discrete problems.

Full work available at URL: https://arxiv.org/abs/1811.05516

Recommendations

• scientific article; zbMATH DE number 2096432
• New results for recognizing convex-\(QP\) adverse graphs
• Recognition of Graphs with Convex Quadratic Stability Number
• A simplex like approach based on star sets for recognizing convex-\(QP\) adverse graphs
• On hereditary properties of the class of graphs with convex quadratic stability number

zbMATH Keywords

convex quadratic programming in graphsrelations between continuous and discrete optimizationstability number of graphs

Mathematics Subject Classification ID

Quadratic programming (90C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Programming involving graphs or networks (90C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Reducibility among combinatorial problems
• Spectra of graphs
• An introduction to the theory of graph spectra
• On the Shannon capacity of a graph
• Paths, Trees, and Flowers
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Title not available (Why is that?)
• Maxima for Graphs and a New Proof of a Theorem of Turán
• On maximal independent sets of vertices in claw-free graphs
• Continuous Characterizations of the Maximum Clique Problem
• Title not available (Why is that?)
• Equitable bipartitions of graphs and related results
• Efficient domination through eigenvalues
• A simplex like approach based on star sets for recognizing convex-\(QP\) adverse graphs
• On standard quadratic optimization problems
• Title not available (Why is that?)
• On hereditary properties of the class of graphs with convex quadratic stability number
• Graphs with least eigenvalue \(-2\) attaining a convex quadratic upper bound for the stability number
• Title not available (Why is that?)
• An upper bound on the independence number of a graph computable in polynomial-time
• A Convex Quadratic Characterization of the Lovász Theta Number
• Title not available (Why is that?)
• A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph
• Improving an upper bound on the stability number of a graph
• A quadratic programming approach to the determination of an upper bound on the weighted stability number
• A surprising property of the least eigenvalue of a graph
• Stability in \(P_5\)- and banner-free graphs
• A heuristic for the stability number of a graph based on convex quadratic programming and tabu search
• Title not available (Why is that?)
• On regular-stable graphs.
• A characterization of the weighted Lovász number based on convex quadratic programming

Cited In (7)

• On hereditary properties of the class of graphs with convex quadratic stability number
• Recognition of Graphs with Convex Quadratic Stability Number
• New results for recognizing convex-\(QP\) adverse graphs
• Title not available (Why is that?)
• Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
• A simplex like approach based on star sets for recognizing convex-\(QP\) adverse graphs
• Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials

This page was built for publication: A survey on graphs with convex quadratic stability number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207733)