• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Working paper

Independence numbers of Johnson-type graphs

Kiselev S., Cherkashin D.
We consider a family of distance graphs in R n and find its independent numbers in some cases. Define graph J±(n, k, t) in the following way: the vertex set consists of all vectors from {−1, 0, 1} n with k nonzero coordinates; edges connect the pairs of vertices with scalar product t. We find the independence number of J±(n, k, t) for n > n0(k, t) in the cases t = 0 and t = −1; these cases for k = 3 are solved completely. Also the independence number is found for negative odd t and n > n0(k, t).