• The automorphism group of the bipartite Kneser graph

    • Fulltext


        Click here to view fulltext PDF

      Permanent link:

    • 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
    • Dates

  • Proceedings – Mathematical Sciences | News

    • Editorial Note on Continuous Article Publication

      Posted on July 25, 2019

      Click here for Editorial Note on CAP Mode

© 2021-2022 Indian Academy of Sciences, Bengaluru.