On the automorphism groups of connected bipartite irreducible graphs

Abstract

Let $G=(V,E)$ be a graph with the vertex-set $V$ and the edge-set $E$. Let $N(v)$ denote the set of neighbors of the vertex $v$ of $G.$ The graph $G$ is called $irreducible$ whenever for every $v,w\in V$ if $v\ne w$, then $N(v)\ne N(w).$ In this paper, we present a method for finding automorphism groups of connected bipartite irreducible graphs. Then, by our method, we determine automorphism groups of some classes of connected bipartite irreducible graphs, including a class of graphs which are derived from Grassmann graphs. Let $a_0$ be a fixed positive integer. We show that if $G$ is a connected non-bipartite irreducible graph such that $c(v,w)=|N(v)\cap N(w)|=a_0$ when $v,w$ are adjacent, whereas $c(v,w)\ne a_0$, when $v,w$ are not adjacent, then $G$ is a $stable$ graph, that is, the automorphism group of the bipartite double cover of $G$ is isomorphic with the group $Aut(G)\times {\mathbb{Z}}_2$. Finally, we show that the Johnson graph $J(n,k)$ is a stable graph.

16 pages

References in corpus (3)

• Automorphism group of the complete transposition graph
• Johnson graphs are panconnected
• The spectrum and automorphism group of the set-inclusion graph