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

DOI10.1016/J.DISC.2023.113471zbMATH Open1514.05051arXiv2212.14060OpenAlexW4367048681MaRDI QIDQ6041879FDOQ6041879

Authors: Lord Clifford Kavi, Mike Newman 

Publication date: 15 May 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Combinatorial Designs
• Title not available (Why is that?)
• Spectra of graphs
• Interlacing eigenvalues and graphs
• Title not available (Why is that?)
• Algebraic Graph Theory
• Mutually orthogonal Latin squares: A brief survey of constructions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Spectral characterization of the Hamming graphs
• Broadcast chromatic numbers of graphs
• The strong chromatic index ofC4-free graphs
• Title not available (Why is that?)
• On the injective chromatic number of graphs
• Title not available (Why is that?)
• Independence and average distance in graphs
• Spectral bounds for the \(k\)-independence number of a graph
• On the \(k\)-independence number of graphs
• Concerning the number of mutually orthogonal latin squares
• On the number of orthogonal latin squares
• A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number
• 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

Cited In (7)

• A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number
• Optimal graphs for independence and \(k\)-independence polynomials
• On the \(k\)-independence number of graphs
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
• Spectral bounds for the \(k\)-independence number of a graph
• The clique number of the exact distance \(t\)-power graph: complexity and eigenvalue bounds
• On inertia and ratio type bounds for the \(k\)-independence number of a graph and their relationship

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)