A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph

DOI10.1023/A:1018965309522zbMath0908.90260MaRDI QIDQ1265892

Carlos J. Luz, Domingos Moreira Cardoso

Publication date: 27 September 1998

Published in: Annals of Operations Research (Search for Journal in Brave)

zbMATH Keywords

quadratic programmingcombinatorial optimizationgraph theoryindependence numberpolynomial-time algorithmmaximum independent set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (9)

Approximating the maximum size of a \(k\)-regular induced subgraph by an upper bound on the co-\(k\)-plex number ⋮ On hereditary properties of the class of graphs with convex quadratic stability number ⋮ A quadratic programming approach to the determination of an upper bound on the weighted stability number ⋮ Improving an upper bound on the stability number of a graph ⋮ A characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programming ⋮ A simplex like approach based on star sets for recognizing convex-\(QP\) adverse graphs ⋮ A characterization of the weighted Lovász number based on convex quadratic programming ⋮ A survey on graphs with convex quadratic stability number ⋮ New results for recognizing convex-QP adverse graphs

This page was built for publication: A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph