On the dissociation number of Kneser graphs

Abstract: A set

D

of vertices of a graph

G

is a dissociation set if each vertex of

D

has at most one neighbor in

D

. The dissociation number of

G

,

d i s s (G)

, is the cardinality of a maximum dissociation set in a graph

G

. In this paper we study dissociation in the well-known class of Kneser graphs

K_{n, k}

. In particular, we establish that the dissociation number of Kneser graphs

K_{n, 2}

equals

m a x n - 1, 6

. We show that for any

k g e q 2

, there exists

n_{0} i n m a t h b b N

such that

d i s s (K_{n, k}) = a l p h a (K_{n, k})

for any

n g e q n_{0}

. We consider the case

k = 3

in more details and prove that

n_{0} = 8

in this case. Then we improve a trivial upper bound

2 a l p h a (K_{n, k})

for the dissociation number of Kneser graphs

K_{n, k}

by using Katona's cyclic arrangement of integers from

1, l d o t s, n

. Finally we investigate the odd graphs, that is, the Kneser graphs with

n = 2 k + 1

. We prove that

d i s s (K_{2 k + 1, k}) = 2 k c h o o s e k

.

This page was built for publication: On the dissociation number of Kneser graphs