Lower bounds on the independence numbers of distance graphs with vertices in \-1, 0, 1\ⁿ

2024/12/22 by Akhiiarov, A. R., Bobu, A. V., Raigorodskii, A. M.
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2412.17120

Abstract

This work is devoted to lower bounds on independence numbers of distance graphs with vertices in \-1,0,1\ⁿ. The asymptotic case is studied, yielding new results over a broad range of parameters. Numerical results are presented, highlighting nontrivial relationships between the obtained bounds. Known upper bounds and their potential suboptimality are discussed separately.

Related

• Independence numbers of Johnson-type graphs
• Sharp upper bounds on the k-independence number in graphs with given minimum and maximum degree
• On the independence ratio of distance graphs
• 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