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

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 paper, we introduce a new family of polynomials obtained from the spectrum of a graph, called minor polynomials. 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. With some examples and infinite families of graphs whose bounds are tight, we also show that the odd graph O with odd has no 1-perfect code. Moreover, we show that our bound coincides, in general, with the Delsarte’s linear programming bound and the Lovász theta number θ, the best ones to our knowledge. In fact, as a byproduct, it is shown that the given bounds also apply for θ and Θ, the Shannon capacity of a graph. Moreover, apart from the possible interest that the minor polynomials can have, our approach has the advantage of yielding closed formulas and, so, allowing asymptotic analysis.