A survey on graphs with convex quadratic stability number
From MaRDI portal
Publication:5207733
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.
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
Cites work
- scientific article; zbMATH DE number 3980484 (Why is no real title available?)
- scientific article; zbMATH DE number 3777544 (Why is no real title available?)
- scientific article; zbMATH DE number 3492724 (Why is no real title available?)
- scientific article; zbMATH DE number 1219584 (Why is no real title available?)
- scientific article; zbMATH DE number 2149405 (Why is no real title available?)
- scientific article; zbMATH DE number 2096432 (Why is no real title available?)
- A Convex Quadratic Characterization of the Lovász Theta Number
- A characterization of the weighted Lovász number based on convex quadratic programming
- A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph
- A heuristic for the stability number of a graph based on convex quadratic programming and tabu search
- A quadratic programming approach to the determination of an upper bound on the weighted stability number
- A simplex like approach based on star sets for recognizing convex-\(QP\) adverse graphs
- A surprising property of the least eigenvalue of a graph
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- An introduction to the theory of graph spectra
- An upper bound on the independence number of a graph computable in polynomial-time
- Continuous Characterizations of the Maximum Clique Problem
- Efficient domination through eigenvalues
- Equitable bipartitions of graphs and related results
- Graphs with least eigenvalue \(-2\) attaining a convex quadratic upper bound for the stability number
- Improving an upper bound on the stability number of a graph
- Maxima for Graphs and a New Proof of a Theorem of Turán
- On hereditary properties of the class of graphs with convex quadratic stability number
- On maximal independent sets of vertices in claw-free graphs
- On regular-stable graphs.
- On standard quadratic optimization problems
- On the Shannon capacity of a graph
- Paths, Trees, and Flowers
- Reducibility among combinatorial problems
- Spectra of graphs
- Stability in \(P_5\)- and banner-free graphs
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
- scientific article; zbMATH DE number 2096432 (Why is no real title available?)
- 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)
