The automorphism group of the bipartite Kneser graph
Click here to view fulltext PDF
Permanent link:
https://www.ias.ac.in/article/fulltext/pmsc/129/03/0034
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.
S MORTEZA MIRAFZAL^{1} ^{}
Volume 131, 2021
All articles
Continuous Article Publishing mode
Click here for Editorial Note on CAP Mode
© 2021-2022 Indian Academy of Sciences, Bengaluru.