The automorphism group of the bipartite Kneser graph

Proceedings of the Indian Academy of Sciences. Mathematical sciences

S MORTEZA MIRAFZAL^1¹ 

[1] Department of Mathematics, Lorestan University, Khoramabad, Iran^1

关键词: Bipartite Kneser graph;    vertex-transitive graph;    automorphism group;   

DOI  :  

学科分类：数学（综合）

来源: Indian Academy of Sciences

【 摘 要 】

Let $n$ and $k$ be integers with$n>2k$,$k\geq1$. We denote by $H(n, k)$ the bipartite Kneser graph, that is, a graph with the family of $k$-subsets and($n-k$)-subsets of $[n]= \{1, 2,\ldots ,n\}$ as vertices, in which any two vertices are adjacent if and only if one of them is a subset of the other. In this paper, we determine the automorphism group of $H(n, k)$. We show that ${\rm Aut}(H(n, k))\cong {\rm Sym}([n]) \times \mathbb{Z}_2$, where $\mathbb{Z}_2$ is the cyclic group of order $2$. Then, as an application of the obtained result, we give a new proof for determining the automorphism group of the Kneser graph $K(n,k)$. In fact, we show how to determine the automorphism group of the Kneser graph $K(n,k)$ given the automorphism group of the Johnson graph$J(n,k)$. Note that the known proofs for determining the automorphism groups of Johnson graph $J(n,k)$ and Kneser graph $K(n,k)$ are independent of each other.

【 授权许可】

CC BY