E-resources
Peer reviewed
Open access
-
Kavi, Lord C.; Newman, Mike
Discrete mathematics, July 2023, 2023-07-00, Volume: 346, Issue: 7Journal Article
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 α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.
