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

DOI10.1016/J.LAA.2020.07.009zbMATH Open1446.05056arXiv1907.08626OpenAlexW3040816021MaRDI QIDQ2197265FDOQ2197265

Authors: Miguel Angel Fiol 

Publication date: 31 August 2020

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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 $llek$, 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_{ell}$ with $ell$ odd has no $1$-perfect code.

Full work available at URL: https://arxiv.org/abs/1907.08626

Recommendations

• The optimal bound on the 3-independence number obtainable from a polynomial-type method
• On inertia and ratio type bounds for the \(k\)-independence number of a graph and their relationship
• Spectral bounds for the \(k\)-independence number of a graph
• On the \(k\)-independence number of graphs
• Sharp upper bounds on the \(k\)-independence number in graphs with given minimum and maximum degree

zbMATH Keywords

spectrumShannon capacityinterlacing\(k\)-independence number\(k\)-partially walk-regularDelsarte's LP boundminor polynomialLovász theta number

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph polynomials (05C31) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Interlacing eigenvalues and graphs
• On the Shannon capacity of a graph
• Problems in algebraic combinatorics
• From local adjacency polynomials to locally pseudo-distance-regular graphs
• On almost distance-regular graphs
• Association schemes and coding theory
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Polynomial of a Graph
• Broadcast chromatic numbers of graphs
• The Chromatic Number of Graph Powers
• The strong chromatic index ofC4-free graphs
• Feasibility conditions for the existence of walk-regular graphs
• Title not available (Why is that?)
• On the injective chromatic number of graphs
• On the algebraic theory of pseudo-distance-regularity around a set
• Title not available (Why is that?)
• Eigenvalue interlacing and weight parameters of graphs
• Some families of orthogonal polynomials of a discrete variable and their applications to graphs and codes
• On a class of polynomials and its relation with the spectra and diameters of graphs
• Independence and average distance in graphs
• An eigenvalue characterization of antipodal distance-regular graphs
• Spectral bounds for the \(k\)-independence number of a graph
• On the \(k\)-independence number of graphs
• Multidiameters and multiplicities
• Distance colouring without one cycle length

Cited In (6)

• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• The optimal bound on the 3-independence number obtainable from a polynomial-type method
• Some applications of the proper and adjacency polynomials in the theory of graph spectra
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
• On inertia and ratio type bounds for the \(k\)-independence number of a graph and their relationship
• The alternating polynomials and their relation with the spectra and conditional diameters of graphs

This page was built for publication: A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197265)