The Diameter of the Generalised Kneser Graphs


Deming Li 1 and Mingju Liu 2
1 Department of Mathematics, Capital Normal University, Beijing 100037, P. R. China
2 LMIB and Department of Mathematics, Beihang University, Beijing 100083, P. R. China


Abstract     Full Text  PDF

Let $[n]=\{1, 2, ..., n\}$ be a set of $n$-elements. The generalised Kneser graph $K(n, r, s)$ is the graph with vertex set $V(K(n, r, s))=\{A:$ $A$ is a $r$-subset of $[n]. \}$ and edge set $E()=\{AB:$ $A, B \in V$ and $|A\cap B|\le s \}$. Here we show that the diameter of $K(n, r, s)$ is $$\lceil\frac{r-s-1}{n-2(r-s)}\rceil+1,$$ which is equal to the result of Valencia-Pabon and Vera if $s=0$.