New Lower Bounds for the Independence Numbers of Distance Graphs with Vertices in {-1,0, l}~n

摘要

Let n = 2k, k ∈N. Consider a graph G_n = (V_n, E_n) for which V_n = {x = (x_1,...,x_n) :x_i ∈{-1,0,1}, |{i : x_i = ±1}| =|{i : x_i = 0} = k}, E_n = {{x,y}:x,y ∈ V_n V_n, |x-y| = 2k~(1/2)}. Assume that the first nonzero coordinate of every vector in V_n is equal to 1. Thus, |V_n| = C_n~k2~(k-1).