Independence numbers of Johnson-type graphs

Abstract: We consider a family of distance graphs in

m a t h b b R^{n}

and find its independent numbers in some cases. Define graph

J_{p m} (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_{p m} (n, k, t)

for

n > n_{0} (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 > n_{0} (k, t)

.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Independence numbers of Johnson-type graphs