Some algebraic properties of bipartite Kneser graphs

Abstract

Let $n$ and $k$ be integers with $n>k\ge 1$ and $[n]=\{1,2,...,n\}$. The $bipartiteKnesergraph$ $H(n,k)$ is the graph with the all $k$-element and all ($n-k$)-element subsets of $[n]$ as vertices, and there is an edge between any two vertices, when one is a subset of the other. In this paper, we show that $H(n,k)$ is an arc-transitive graph. Also, we show that $H(n,1)$ is a distance-transitive Cayley graph. Finally, we determine the automorphism group of the graph $H(n,1)$ and show that $Aut(H(n,1))\cong Sym([n])$ $\times {\mathbb{Z}}_2$, where ${\mathbb{Z}}_2$ is the cyclic group of order $2$. Moreover, we pose some open problems about the automorphism group of the bipartite Kneser graph $H(n,k)$.

To appear in Ars Combinatoria. arXiv admin note: text overlap with arXiv:1803.02524