On the k-independence number of graphs

This paper generalizes and unifies the existing spectral bounds on the k-independence number of a graph, which is the maximum size of a set of vertices at pairwise distance greater than k. The previous bounds known in the literature follow as a corollary of the main results in this work. We show tha...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2019-10, Vol.342 (10), p.2875-2885
Main Authors: Abiad, A., Coutinho, G., Fiol, M.A.
Format: Article
Language:English
Subjects:
05 Combinatorics
05C Graph theory
[formula omitted]-independence number
Antipodal distance-regular graph
Classificació AMS
Grafs, Teoria de
Graph
Graph theory
Interlacing
k-independence number
Matemàtica discreta
Matemàtiques i estadística
Regular partition
Spectrum
Teoria de grafs
Àrees temàtiques de la UPC
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper generalizes and unifies the existing spectral bounds on the k-independence number of a graph, which is the maximum size of a set of vertices at pairwise distance greater than k. The previous bounds known in the literature follow as a corollary of the main results in this work. We show that for most cases our bounds outperform the previous known bounds. Some infinite families of graphs where the bounds are tight are also presented. Finally, as a byproduct, we derive some spectral lower bounds for the diameter of a graph.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2019.01.016