A new class of polynomials from to the spectrum of a graph, and its application to bound the k-independence number

2019/07/19 by Fiol, M. A. · 4 citations
#05C50 #05C69 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1907.08626

Abstract

The k-independence number of a graph is the maximum size of a set of vertices at pairwise distance greater than k. A graph is called k-partially walk-regular if the number of closed walks of a given length l≤ k, rooted at a vertex v, only depends on l. In particular, a distance-regular graph is also k-partially walk-regular for any k. In this note, we introduce a new family of polynomials obtained from the spectrum of a graph. These polynomials, together with the interlacing technique, allow us to give tight spectral bounds on the k-independence number of a k-partially walk-regular graph. Together with some examples where the bounds are tight, we also show that the odd graph O_ℓ with ℓ odd has no 1-perfect code.

Cited by

• The Shannon capacity of graph powers
• The multilinear forms Cayley graph and the eigenvalue method for tensor codes
• The Eigenvalue Method in Coding Theory
• Eigenvalue bounds for distance-edge colorings

Related

• Spectral bounds for the k-independence number of a graph
• On the k-independence number of graphs
• On inertia and ratio type bounds for the k-independence number of a graph and their relationship
• On the regular k-independence number of graphs
• Sharp upper bounds on the k-independence number in graphs with given minimum and maximum degree