Some algebraic properties of bipartite Kneser graphs

arXiv1804.04570MaRDI QIDQ6300275

Ali Zafari, S. M. Mirafzal

Publication date: 12 April 2018

Abstract: Let $n$ and $k$ be integers with $n>kgeq1$ and $[n]=1,2,...,n$. The $bipartiteKnesergraph$ $H(n,k)$ is the graph with the all $k$-element and all ($n-k$)-element subsets of $[n]$ as vertices, and there is an edge between any two vertices, when one is a subset of the other. In this paper, we show that $H(n,k)$ is an arc-transitive graph. Also, we show that $H(n,1)$ is a distance-transitive Cayley graph. Finally, we determine the automorphism group of the graph $H(n,1)$ and show that $Aut(H(n,1))congSym([n])$ $imesmathbb{Z}_2$, where $mathbb{Z}_2$ is the cyclic group of order $2$. Moreover, we pose some open problems about the automorphism group of the bipartite Kneser graph $H(n,k)$.

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Applications of graph theory to circuits and networks (94C15)

This page was built for publication: Some algebraic properties of bipartite Kneser graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6300275)