Spectral bounds for the k-independence number of a graph

DOI10.1016/J.LAA.2016.08.024zbMATH Open1352.05107arXiv1510.07186OpenAlexW2229314495MaRDI QIDQ501229FDOQ501229

Authors: Aida Abiad, Sebastian Cioaba, Michael Tait 

Publication date: 29 December 2016

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

Abstract: In this paper, we obtain two spectral upper bounds for the $k$-independence number of a graph which is is the maximum size of a set of vertices at pairwise distance greater than $k$. We construct graphs that attain equality for our first bound and show that our second bound compares favorably to previous bounds on the $k$-independence number.

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

Recommendations

• On the \(k\)-independence number of graphs
• Sharp upper bounds on the \(k\)-independence number in graphs with given minimum and maximum degree
• Spectral upper bound on the quantum \(k\)-independence number of a graph
• The bounds of spectral radius of graphs with a given size of independent set.
• The optimal bound on the 3-independence number obtainable from a polynomial-type method

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)

Cites Work

• Spectra of graphs
• Interlacing eigenvalues and graphs
• Title not available (Why is that?)
• Locally pseudo-distance-regular graphs
• Title not available (Why is that?)
• A Tight Bound on the Irregularity Strength of Graphs
• Explicit construction of linear sized tolerant networks
• Broadcast chromatic numbers of graphs
• Pseudo-random graphs
• The strong chromatic index ofC4-free graphs
• Algebraic characterizations of distance-regular graphs
• On the injective chromatic number of graphs
• Title not available (Why is that?)
• Eigenvalue interlacing and weight parameters of graphs
• Title not available (Why is that?)
• An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs
• The alternating and adjacency polynomials, and their relation with the spectra and diameters of 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
• Laplacian eigenvalues of the second power of a graph
• Large 2-independent sets of regular graphs
• A Cauchy-Davenport type result for arbitrary regular graphs
• On the $b$ -Independence Number of Sparse Random Graphs
• Average degree in graph powers

Cited In (17)

• A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number
• Laplacian spectral bounds for clique and independence numbers of graphs
• Integer indices and spectral properties for the \(KK_n^j\) graphs
• The optimal bound on the 3-independence number obtainable from a polynomial-type method
• The \(k\)-independence number of \(t\)-connected graphs
• On the \(k\)-independence number of graphs
• Title not available (Why is that?)
• Bounds for the independence number in \(k\)-step Hamiltonian graphs
• A unified framework for the expander mixing lemma for irregular graphs and its applications
• Sharp upper bounds on the \(k\)-independence number in graphs with given minimum and maximum degree
• On trees with given diameter and extremal number of distance-\(k\) independent sets
• Spectral Bounds for the k-Regular Induced Subgraph Problem
• 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
• The bounds of spectral radius of graphs with a given size of independent set.
• Spectral upper bounds for the order of a \(k\)-regular induced subgraph
• On inertia and ratio type bounds for the \(k\)-independence number of a graph and their relationship

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

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