A relative bound for independence

DOI10.1016/J.DISC.2019.111607zbMATH Open1422.05082arXiv1901.00585OpenAlexW2966780022WikidataQ127402697 ScholiaQ127402697MaRDI QIDQ2329192FDOQ2329192

Authors: Bogdan Nica 

Publication date: 17 October 2019

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We prove an upper bound for the independence number of a graph in terms of the largest Laplacian eigenvalue, and of a certain induced subgraph. Our bound is a refinement of a well-known Hoffman-type bound.

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

Recommendations

• A new eigenvalue bound for independent sets
• Eigenvalue bounds for independent sets
• A new upper bound for eigenvalues of the Laplacian matrix of a graph
• Upper bound for the Laplacian graph eigenvalues
• Upper bounds on the independence and the clique covering number

zbMATH Keywords

Laplacian eigenvalueindependence number

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Interlacing eigenvalues and graphs
• Eigenvalue bounds for independent sets
• Graphs with constant \(\mu\) and \(\overline{\mu}\)
• On Graphs that do not Contain a Thomsen Graph
• Laplacian spectral bounds for clique and independence numbers of graphs
• On the Lovász \(\vartheta\)-number of almost regular graphs with application to Erdős-Rényi graphs
• The independence number for polarity graphs of even order planes
• On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph
• Title not available (Why is that?)
• On the two conjectures of Graffiti

Cited In (11)

• Eigenvalue bounds for independent sets
• Hoffman's ratio bound
• Upper bounds on the independence and the clique covering number
• Bounded Independence Fools Halfspaces
• On the independence number of regular graphs of matrix rings
• Tight Probability Bounds with Pairwise Independence
• Title not available (Why is that?)
• Weighted matrix eigenvalue bounds on the independence number of a graph
• Study on the upper bound of the dependence number
• Around -independence
• A graph for which the inertia bound is not tight

This page was built for publication: A relative bound for independence

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