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$, $diss(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 $\max \{n-1,6\}$. We show that for any $k\ge 2$, there exists $n_0\in \mathbb{N}$ such that $diss(K_{n,k})=\alpha (K_{n,k})$ for any $n\ge 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\alpha (K_{n,k})$ for the dissociation number of Kneser graphs $K_{n,k}$ by using Katona's cyclic arrangement of integers from $\{1,\dots ,n\}$. Finally we investigate the odd graphs, that is, the Kneser graphs with $n=2k+1$. We prove that $diss(K_{2k+1,k})=\left(\genfrac{}{}{0ex}{}{2k}{k}\right)$.

9 pages, 1 figure

References in corpus (1)

• Minimum k-path vertex cover