On the k-independence number of graphs

A. Abiad*, G. Coutinho, M. A. Fiol

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)2875-2885
Number of pages11
JournalDiscrete Mathematics
Volume342
Issue number10
DOIs
Publication statusPublished - Oct 2019
EventAlgebraic and Extremal Graph Theory Conference - University of Delaware, Newark, United States
Duration: 7 Aug 201710 Aug 2017

Keywords

  • Graph
  • k-independence number
  • Spectrum
  • Interlacing
  • Regular partition
  • Antipodal distance-regular graph
  • CHROMATIC NUMBER
  • DISTANCE
  • POLYNOMIALS

Cite this