Spectral bounds for the \(k\)-independence number of a graph

DOI10.1016/j.laa.2016.08.024zbMath1352.05107arXiv1510.07186OpenAlexW2229314495MaRDI QIDQ501229

Aida Abiad, Sebastian M. Cioabă, Michael Tait

Publication date: 29 December 2016

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

eigenvaluesgraph powers\(k\)-independence numberexpander-mixing lemma

Mathematics Subject Classification ID

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

Related Items (8)

Sharp upper bounds on the \(k\)-independence number in graphs with given minimum and maximum degree ⋮ The optimal bound on the 3-independence number obtainable from a polynomial-type method ⋮ A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number ⋮ On inertia and ratio type bounds for the \(k\)-independence number of a graph and their relationship ⋮ The \(k\)-independence number of \(t\)-connected graphs ⋮ Spectral upper bound on the quantum k-independence number of a graph ⋮ Optimization of eigenvalue bounds for the independence and chromatic number of graph powers ⋮ On the \(k\)-independence number of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spectra of graphs
• Explicit construction of linear sized tolerant networks
• Locally pseudo-distance-regular graphs
• The alternating and adjacency polynomials, and their relation with the spectra and diameters of graphs
• Eigenvalue interlacing and weight parameters of graphs
• Algebraic characterizations of distance-regular graphs
• The alternating polynomials and their relation with the spectra and conditional diameters of graphs
• Independence and average distance in graphs
• An eigenvalue characterization of antipodal distance-regular graphs
• On the injective chromatic number of graphs
• Interlacing eigenvalues and graphs
• Laplacian eigenvalues of the second power of a graph
• A Cauchy–Davenport Type Result for Arbitrary Regular Graphs
• A Tight Bound on the Irregularity Strength of Graphs
• The strong chromatic index ofC4-free graphs
• On the $b$ -Independence Number of Sparse Random Graphs
• Average Degree in Graph Powers
• An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs

This page was built for publication: Spectral bounds for the \(k\)-independence number of a graph