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

DOI10.1023/A:1018965309522zbMATH Open0908.90260MaRDI QIDQ1265892FDOQ1265892

Authors: Carlos J. Luz, D. M. Cardoso 

Publication date: 27 September 1998

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

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

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)

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
• Title not available (Why is that?)
• 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 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
• New results for recognizing convex-QP adverse graphs
• 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)