The optimal bound on the 3-independence number obtainable from a polynomial-type method

DOI10.1016/J.DISC.2023.113471MaRDI QIDQ6041879zbMATH OpenOpenAlexFDO

Authors Lord Clifford Kavi, Mike Newman

Publication date 15 May 2023

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

spectrumHamming graphinterlacing\(k\)-independence number

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12) Structural characterization of families of graphs (05C75)

Abstract: A $k$-independent set in a connected graph is a set of vertices such that any two vertices in the set are at distance greater than $k$ in the graph. The $k$-independence number of a graph, denoted $alph{a}_k$, is the size of a largest $k$-independent set in the graph. Recent results have made use of polynomials that depend on the spectrum of the graph to bound the $k$-independence number. They are optimized for the cases $k=1,2$. There are polynomials that give good (and sometimes) optimal results for general $k$, including case $k=3$. In this paper, we provide the best possible bound that can be obtained by choosing a polynomial for case $k=3$ and apply this bound to well-known families of graphs including the Hamming graph.

Recommendations

• A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number
• Spectral bounds for the \(k\)-independence number of a graph
• Optimal graphs for independence and \(k\)-independence polynomials
• 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 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 428989 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 637355 (Why is no real title available?)
• scientific article; zbMATH DE number 3377258 (Why is no real title available?)
• A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number
• Algebraic Graph Theory
• Broadcast chromatic numbers of graphs
• Combinatorial Designs
• Concerning the number of mutually orthogonal latin squares
• Independence and average distance in graphs
• Interlacing eigenvalues and graphs
• Mutually orthogonal Latin squares: A brief survey of constructions
• On inertia and ratio type bounds for the \(k\)-independence number of a graph and their relationship
• On the \(k\)-independence number of graphs
• On the injective chromatic number of graphs
• On the number of orthogonal latin squares
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
• Spectra of graphs
• Spectral bounds for the \(k\)-independence number of a graph
• Spectral characterization of the Hamming graphs
• The strong chromatic index ofC4-free graphs

Cited in

(7)

• The clique number of the exact distance \(t\)-power graph: complexity and eigenvalue bounds
• On the \(k\)-independence number of graphs
• Optimal graphs for independence and \(k\)-independence polynomials
• A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number
• 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
• Spectral bounds for the \(k\)-independence number of a graph

This page was built for publication: The optimal bound on the 3-independence number obtainable from a polynomial-type method

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