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

DOI10.1023/A:1018965309522MaRDI QIDQ1265892zbMATH OpenFDO

Authors Carlos J. Luz, D. M. Cardoso

Publication date 27 September 1998

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

zbMATH Keywords

quadratic programmingcombinatorial optimizationgraph theorypolynomial-time algorithmindependence numbermaximum independent set

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 434686
• An upper bound for the number of independent sets in regular graphs
• Upper bounds for independent domination in regular graphs
• A new lower bound on the independence number of graphs
• The upper and lower independence number of graphs
• Upper bounds for the independence polynomial of graphs at \(-1\)
• An improved lower bound on the independence number of a graph
• A lower bound on the independence number of a graph
• scientific article; zbMATH DE number 1112370
• On Selkow's bound on the independence number of graphs

Cited in

(12)

• 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
• scientific article; zbMATH DE number 1820188 (Why is no real title available?)
• Improving an upper bound on the stability number of a graph
• New results for recognizing convex-\(QP\) adverse graphs
• A quadratic programming approach to the determination of an upper bound on the weighted stability number
• A survey on graphs with convex quadratic stability number
• The maximum independent union of cliques problem: complexity and exact approaches
• 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
• On the Lovász \(\vartheta\)-number of almost regular graphs with application to Erdős-Rényi graphs

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

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