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.009MaRDI QIDQ2197265zbMATH OpenOpenAlexFDO

Authors Miguel Angel Fiol

Publication date 31 August 2020

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

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

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)

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.

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

Cites work

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

Cited in

(6)

• 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
• The alternating polynomials and their relation with the spectra and conditional diameters of graphs
• On inertia and ratio type bounds for the \(k\)-independence number of a graph and their relationship
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey

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)