• S MORTEZA MIRAFZAL

Articles written in Proceedings – Mathematical Sciences

• The automorphism group of the bipartite Kneser graph

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.

• Johnson graphs are panconnected

For any given $n,m \in \mathbb{N}$ with $m$ < $n$, the Johnson graph $J(n,m)$ is defined as the graph whose vertex set is $V=\{v\mid v\subseteq [n]=\{1,\ldots,n\}, |v|=m\}$, where two vertices $v$, $w$ are adjacent if and only if $|v\cap w|=m-1$. A graph $G$ of order $n$ > $2$ is panconnected if for every two vertices $u$ and $v$, there is a $u-v$ path of length $l$ for every integer $l$ with $d(u,v) \leq l \leq n-1$. In this paper, we prove that the Johnson graph $J(n,m)$ is a panconnected graph.

• On the automorphism groups of connected bipartite irreducible graphs

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\neq w$, then $N(v) \neq 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) = \mid N(v)∩ N(w)\mid = a_0$ when $v, w$ areadjacent, whereas $c(v,w) \neq 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 ${\rm Aut}(G) \times \mathbb{Z}_2$. Finally, we show that the Johnson graph $J (n, k)$ is a stable graph.

• # Proceedings – Mathematical Sciences

Volume 131, 2021
All articles
Continuous Article Publishing mode

• # Editorial Note on Continuous Article Publication

Posted on July 25, 2019