pith. sign in

arxiv: 1803.02524 · v3 · pith:QEHUGNCZnew · submitted 2018-03-07 · 🧮 math.GR

The automorphism group of the bipartite Kneser graph

classification 🧮 math.GR
keywords graphautomorphismgroupkneserbipartitedeterminedeterminingjohnson
0
0 comments X
read the original 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, ... , 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 $Aut(H(n, k))\cong 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 from each other.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.