• The automorphism group of the bipartite Kneser graph

• # Fulltext

https://www.ias.ac.in/article/fulltext/pmsc/129/03/0034

• # Keywords

Bipartite Kneser graph; vertex-transitive graph; automorphism group

• # Abstract

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.

• # Author Affiliations

1. Department of Mathematics, Lorestan University, Khoramabad, Iran

• # Proceedings – Mathematical Sciences

Volume 131, 2021
All articles
Continuous Article Publishing mode

• # Editorial Note on Continuous Article Publication

Posted on July 25, 2019