Title:
|
On the k-independence number of graphs
|
Author:
|
Abiad, Aida; Coutinho, Gabriel; Fiol Mora, Miquel Àngel
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions |
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.Weshow 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. |
Abstract:
|
Peer Reviewed |
Subject(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs -Graph theory -k-independence number -Spectrum -Interlacing -Regular partition -Antipodal distance-regular graph -Grafs, Teoria de -Classificació AMS::05 Combinatorics::05C Graph theory |
Rights:
|
|
Document type:
|
Article - Submitted version Article |
Share:
|
|