00footnotetext:  The work was supported by Hainan Provincial Natural Science
Foundation of China (No. 122RC652).
E-mail address<EMAIL_ADDRESS>
# Automorphism group of the graph $A(n,k,r)$
Dedicated to my PhD supervisor Xiuyun Guo’s 70th birthday.

Junyao Pan

School of Sciences, Wuxi University, Wuxi, Jiangsu,
214105 People’s Republic of China

Abstract: Let $[n]^{(k)}$ be the set of all ordered $k$-tuples of distinct
elements in $[n]=\\{1,2,...,n\\}$. The $(n,k,r)$-arrangement graph $A(n,k,r)$
with $1\leq r\leq k\leq n$, is the graph with vertex set $[n]^{(k)}$ and with
two $k$-tuples are adjacent if they differ in exactly $r$ coordinates. In this
manuscript, we characterize the full automorphism groups of $A(n,k,r)$ in the
cases that $1\leq r=k\leq n$ and $r=2<k=n$. Thus, we resolve two special cases
of an open problem proposed by Fu-Gang Yin, Yan-Quan Feng, Jin-Xin Zhou and
Yu-Hong Guo. In addition, we conclude with a bold conjecture.

Keywords: Automorphism group, $(n,k,r)$-arrangement graph.

Mathematics Subject Classification: 05C25, 05E18.

##  1 Introduction

Throughout this paper, $[n]$ denotes the standard $n$-element set
$\\{1,2,...,n\\}$; $[n]^{(k)}$ stands for the set of all ordered $k$-tuples of
distinct elements in $[n]$; $S_{n}$ expresses the symmetric group on $[n]$. In
addition, some notions and notations about permutation groups can be seen in
[2, 7].

The _$(n,k)$ -arrangement graph_ $A(n,k)$ with $1\leq k\leq n-1$, is defined
to have vertex set $[n]^{(k)}$ with two vertices $[s_{1},s_{2},...,s_{k}]$ and
$[t_{1},t_{2},...,t_{k}]$ are adjacent if and only if $|\\{i|s_{i}\neq
t_{i},1\leq i\leq k\\}|=1$. Actually, the arrangement graph was firstly
introduced and studied by Day and Tripathi in [5] as interconnection network
topology, which generalizes the star graph topology in [1]. Since then a fair
amount of work has been done on the arrangement graphs in the literature, for
example [4, 3, 14, 20]. Chen et al [3] generalized the $(n,k)$-arrangement
graph $A(n,k)$ to so called _$(n,k,r)$ -arrangement graph_ $A(n,k,r)$. The
$(n,k,r)$-arrangement graph $A(n,k,r)$ with $1\leq r\leq k\leq n$ has vertex
set $[n]^{(k)}$ with two vertices $[s_{1},s_{2},...,s_{k}]$ and
$[t_{1},t_{2},...,t_{k}]$ are adjacent if and only if $|\\{i|s_{i}\neq
t_{i},1\leq i\leq k\\}|=r$. Yin et al [20] not only investigated the symmetry
property of $(n,k)$-arrangement graph but also proposed the following open
problem.

######  Question 1.1.

([20, Question 5.1] ) Determine the automorphism group of the
$(n,k,r)$-arrangement graph $A(n,k,r)$ with $2\leq r\leq k\leq n$.

Given an undirected graph $\Gamma=(V,E)$ with vertex set $V$ and edge set $E$.
Let $f$ be a bijection from $V$ to $V$ such that $(\alpha^{f},\beta^{f})\in E$
if and only if $(\alpha,\beta)\in E$ for all $\alpha,\beta\in V$. Then $f$ is
called an _automorphism_ of $\Gamma$, and the _full automorphism group_ of
$\Gamma$ is denote by $Aut(\Gamma)$. Actually, the research on the
automorphism groups of some graphs has always been an interesting topic, for
examples [8, 9, 12, 13, 15, 16, 17, 19]. Thereby, we are interested in
Question 1.1. Consider $A(n,k,r)$ with $2\leq r\leq k\leq n$. Motivated by [5,
20], for each $g\in S_{n}$, define the permutation $P(g)$ on $[n]^{(k)}$ by

$[s_{1},s_{2},...,s_{k}]^{P(g)}=[s^{g}_{1},s^{g}_{2},...,s^{g}_{k}],[s_{1},s_{2},...,s_{k}]\in[n]^{(k)};$

for each $h\in S_{k}$, define the permutation $Q(h)$ on $[n]^{(k)}$ by

$[s_{1},s_{2},...,s_{k}]^{Q(h)}=[s_{1^{h^{-1}}},s_{2^{h^{-1}}},...,s_{k^{h^{-1}}}],[s_{1},s_{2},...,s_{k}]\in[n]^{(k)}.$

Clearly, $P(S_{n})$ and $Q(S_{k})$ are also two subgroups of $Aut(A(n,k,r))$.
Furthermore, one easily checks that $P(S_{n})Q(S_{k})=P(S_{n})\times Q(S_{k})$
and $B_{[1,2,...,k]}\cong S_{k}\times S_{n-k}$, where $B_{[1,2,...,k]}$ is the
stabilizer of $P(S_{n})Q(S_{k})$ at $[1,2,...,k]$. In other words, the [20,
Lemma 3.1, 3.2] still hold when $1<r\leq k\leq n$. However, it seems to be
rather difficult to obtain some results as the [20, Lemma 3.4] which plays a
crucial role in proving [20, Theorem 1.1]. Perhaps for this reason, there has
been no progress on this open problem so far.

In this manuscript, we investigate the Question 1.1 from another perspective.
Let $\Gamma=(V,E)$ be an undirected graph with vertex set $V$ and edge set
$E$. If $S\subseteq V$ such that there does not exist edge between $\alpha$
and $\beta$ for any two vertices $\alpha,\beta\in S$, then $S$ is called an
_independent set_ of $\Gamma$. If $S$ is an independent set while
$S\cup\\{\gamma\\}$ is not an independent set for each $\gamma\in V\setminus
S$, then $S$ is called a _maximal independent set_. If $S$ is a maximal
independent set such that $|S|\geq|T|$ for any other maximal independent set
$T$, then $S$ is called a _maximum independent set_. Let $\Omega$ denote the
set of all maximum independent sets of $\Gamma$. Obviously, $Aut(\Gamma)$
induces a permutation group on $\Omega$. This is precisely our breakthrough
point, which we resolve Question 1.1 in the cases that $1\leq r=k\leq n$ and
$r=2<k=n$ by constructing maximum independent sets and isomorphic graphs.

######  Theorem 1.2.

If $n>2$, then

$\displaystyle Aut(A(n,k,r))$ $\displaystyle\cong\begin{cases}P(S_{n})\times
Q(S_{k})&\text{if }r=k<n,\\\ [P(S_{n})\times Q(S_{n})]\rtimes Z_{2}&\text{if
}r=k=n,\\\ [P(S_{n})\times Q(S_{n})]\rtimes Z_{2}&\text{if
}r=2,k=n.\end{cases}$

Here, $Z_{2}=\langle h\rangle$ and $h$ is the map that
$[s_{1},s_{2},...,s_{n}]^{h}=[x_{1},x_{2},...,x_{n}]$ where $x_{j}=i$ if
$s_{i}=j$ for $j=1,2,...,n$.

However, the maximum independent set of $A(n,k,r)$ becomes complicated when
$r<k$. So we cannot determine the automorphism group of $A(n,k,r)$ in this
case except $r=2,k=n$. But, in the light of some special phenomena, we
conclude with some remarks and a bold conjecture.

##  2 Proof of Theorem 1.2

Now we start from constructing maximum independent sets of $A(n,k,k)$. For a
pair of number $(i,j)$ with $i\in[n]$ and $j\in[k]$, we define a subset of
$[n]^{(k)}$ as follows:

$\Delta_{ij}=\\{[s_{1},s_{2},...,s_{j},...,s_{k}]|s_{j}=i,s_{t}\in[n]\setminus\\{i\\}~{}{\rm{for~{}all}}~{}t\in[k]\setminus\\{j\\}\\}.$

For convenience, we set

$\Omega=\\{\Delta_{ij}|i\in[n],j\in[k]\\}.$

Clearly, $\Delta_{ij}$ is a maximal independent set of $A(n,k,k)$. Indeed, we
observe that $\Delta_{ij}$ is a maximum independent set of $A(n,k,k)$, and
there is the following result.

######  Proposition 2.1.

Let $S\subseteq[n]^{(k)}$ with $n>2$. Then $S$ is a maximum independent set of
$A(n,k,k)$ if and only if $S\in\Omega$.

Proof Let $[s_{1},s_{2},...,s_{k}]$ and $[t_{1},t_{2},...,t_{k}]$ be two
distinct $k$-tuples in $[n]^{(k)}$. If there exists an $i\in[k]$ such that
$s_{i}=t_{i}$, then we say that $[s_{1},s_{2},...,s_{k}]$ and
$[t_{1},t_{2},...,t_{k}]$ are intersecting. Thus, $[s_{1},s_{2},...,s_{k}]$
and $[t_{1},t_{2},...,t_{k}]$ are not adjacent in $A(n,k,k)$ if and only if
$[s_{1},s_{2},...,s_{k}]$ and $[t_{1},t_{2},...,t_{k}]$ are intersecting.
Therefore, $S$ is an independent set of $A(n,k,k)$ if and only if $S$ is an
intersecting family. On the other hand, $[s_{1},s_{2},...,s_{k}]$ can be
viewed as an injection from $[k]$ to $[n]$ under the rule $i\mapsto s_{i}$ for
$i=1,2,...,k$. By [10], $[s_{1},s_{2},...,s_{k}]$ and
$[t_{1},t_{2},...,t_{k}]$ are intersecting if and only if they are
intersecting as injections. Apply [10, Theorem 2.1], we deduce this
proposition immediately. $\Box$

It follows from Proposition 2.1 that $Aut(A(n,k,k))$ induces a permutation
group acting on $\Omega$, denoted by $Aut(A(n,k,k))|_{\Omega}$. It is well-
known that there exists a natural surjective homomorphism

$\varphi:~{}Aut(A(n,k,k))\rightarrow Aut(A(n,k,k))|_{\Omega}.$

Apply the fundamental homomorphism theorem, we deduce that

$Aut(A(n,k,k))/ker\varphi\cong Aut(A(n,k,k))|_{\Omega},$

where the kernel $Ker\varphi$ consists of all automorphisms in $Aut(A(n,k,k))$
which fix every $\Delta_{ij}$ in $\Omega$. In particular, if $ker\varphi=1$
then $Aut(A(n,k,k))\cong Aut(A(n,k,k))|_{\Omega}$, where $ker\varphi=1$ means
that the kernel of $\varphi$ is trivial. In fact, we discover that
$ker\varphi=1$ for all $n>2$. Next we recall some notions and notations which
are used in proving this discovery.

Let $\alpha$ and $\beta$ be two vertices of an undirected graph $\Gamma=(V,E)$
with vertex set $V$ and edge set $E$. If there exists an edge between $\alpha$
and $\beta$ in $\Gamma$, then $\alpha$ and $\beta$ are called _neighbor_ (see
[18]). We use $N(\alpha)$ to stand for the collection of all neighbours of
vertex $\alpha$. In addition, for $S\subseteq V$, we define
$N(S)=\bigcap\limits_{\alpha\in S}N(\alpha)$. Next we start to prove
$ker\varphi=1$ from a well-known fact.

######  Fact 2.2.

Let $\Gamma=(V,E)$ be an undirected graph. Then for any $S\subseteq V$ and
$g\in Aut(\Gamma)$,

$N(S)^{g}=N(S^{g}).$

######  Proposition 2.3.

Let $\varphi$ be the natural surjective homomorphism

$\varphi:~{}Aut(A(n,k,k))\rightarrow Aut(A(n,k,k))|_{\Omega}$

with $n>2$. Then $ker\varphi=1$.

Proof Proof by contradiction. Suppose that there exists an automorphism $f\in
Aut(A(n,k,k))$ such that $f$ is a non-identity while fixes every $\Delta_{ij}$
in $\Omega$. Assume that $[s_{1},s_{2},...,s_{k}]^{f}=[t_{1},t_{2},...,t_{k}]$
with $[s_{1},s_{2},...,s_{k}]\neq[t_{1},t_{2},...,t_{k}]$. Thereby, $s_{i}\neq
t_{i}$ for some $i$. Note that

$N([s_{1},s_{2},...,s_{k}])\cap\Delta_{t_{i}i}\neq\emptyset~{}{\rm{and}}~{}N([t_{1},t_{2},...,t_{k}])\cap\Delta_{t_{i}i}=\emptyset.$

On the other hand, by Fact 2.2 we see that
$N([s_{1},s_{2},...,s_{k}])^{f}=N([t_{1},t_{2},...,t_{k}])$. Therefore,

$(N([s_{1},s_{2},...,s_{k}])\cap\Delta_{t_{i}i})^{f}=N([s_{1},s_{2},...,s_{k}]^{f})\cap(\Delta_{t_{i}i})^{f}=N([t_{1},t_{2},...,t_{k}])\cap\Delta_{t_{i}i}.$

This is a contradiction, as desired. $\Box$

Let $G$ be a transitive permutation group acting on $[n]$. A non-empty subset
$\Theta$ of $[n]$ is called a _block_ for $G$ if for each $g\in G$ either
$\Theta^{g}=\Delta$ or $\Theta^{g}\cap\Theta=\emptyset$. Clearly, the
singletons $\\{i\\}$ $(i\in[n])$ and $[n]$ are blocks, and these blocks are
called _trivial_ blocks. Any others are called _nontrivial_ blocks. Put
$\Sigma=\\{\Theta^{g}|g\in G\\}$, where $\Theta$ is a block of $G$. We call
$\Sigma$ the _system of blocks_ containing $\Theta$.

######  Proposition 2.4.

Let $\Sigma=\\{\Omega_{1},\Omega_{2},...,\Omega_{n}\\}$, where
$\Omega_{i}=\\{\Delta_{i1},\Delta_{i2},...,\Delta_{ik}\\}$ for $i\in[n]$. If
$k<n$, then $\Sigma$ is a system of blocks of $Aut(A(n,k,k))|_{\Omega}$ acting
on $\Omega$.

Proof It suffices to prove that either $(\Omega_{i})^{g}=\Omega_{i}$ or
$(\Omega_{i})^{g}\cap\Omega_{i}=\emptyset$ for every $g\in Aut(A(n,k,k))$ and
$i\in[n]$. Proof by contradiction. Suppose that there exists an automorphism
$g\in Aut(A(n,k,k))$ such that $(\Omega_{i})^{g}\neq\Omega_{i}$ and
$(\Omega_{i})^{g}\cap\Omega_{i}\neq\emptyset$ for some $i$. In other words,
there exist $a,b,c,d,j$ such that $(\Delta_{ia})^{g}=\Delta_{ib}$ and
$(\Delta_{ic})^{g}=\Delta_{jd}$ and $i\neq j$ and $a\neq c$.

Since $a\neq c$, we deduce that $\Delta_{ia}\cap\Delta_{ic}=\emptyset$.
Thereby, $\Delta_{ib}\cap\Delta_{jd}=\emptyset$, and so $b=d$. In addition,
$k<n$ implies that we can take $[s_{1},...,s_{b-1},i,s_{b+1},...,s_{k}]$ and
$[s_{1},...,s_{b-1},j,s_{b+1},...,s_{k}]$ in $\Delta_{ib}$ and $\Delta_{jd}$
respectively. Suppose $\alpha^{g}=[s_{1},...,s_{b-1},i,s_{b+1},...,s_{k}]$ and
$\beta^{g}=[s_{1},...,s_{b-1},j,s_{b+1},...,s_{k}]$. Clearly,
$\alpha\in\Delta_{ia}$ and $\beta\in\Delta_{ic}$. Thus, we can set

$\alpha=[t_{1},...,t_{a-1},i,t_{a+1},...,t_{k}]~{}{\rm{and}}~{}\beta=[r_{1},...,r_{c-1},i,r_{c+1},...,r_{k}].$

Note that

$[x_{1},x_{2},...,x_{k}]\in N([s_{1},...s_{b-1},i,s_{b+1},...,s_{k}])\cap
N([s_{1},...s_{b-1},j,s_{b+1},...,s_{k}])$

if and only if $x_{b}\not\in\\{i,j\\}$ and $x_{m}\not\in\\{s_{m}\\}$ for each
$m\in[k]\setminus\\{b\\}$. By the same token,

$[y_{1},y_{2},...,y_{k}]\in N([t_{1},...,t_{a-1},i,t_{a+1},...,t_{k}])\cap
N([r_{1},...,r_{c-1},i,r_{c+1},...,r_{k}])$

if and only if $y_{a}\not\in\\{i,r_{a}\\}$ and $y_{c}\not\in\\{i,t_{c}\\}$ and
$y_{m}\not\in\\{r_{m},t_{m}\\}$ for each $m\in[k]\setminus\\{a,c\\}$. Since
$a\neq c$, we have $r_{a}\neq i$ and $s_{c}\neq i$. Thereby, we see that

$|[N(\alpha)\cap N(\beta)]^{g}|<|N([s_{1},...s_{b-1},i,s_{b+1},...,s_{k}])\cap
N([s_{1},...s_{b-1},j,s_{b+1},...,s_{k}])|.$

However, this is contradict to the Fact 2.2. Thus, $\Sigma$ is a system of
blocks of $Aut(A(n,k,k))|_{\Omega}$ acting on $\Omega$. $\Box$

######  Proposition 2.5.

Let $\Sigma^{\prime}=\\{\Omega^{1},\Omega^{2},...,\Omega^{k}\\}$, where
$\Omega^{j}=\\{\Delta_{1j},\Delta_{2j},...,\Delta_{nj}\\}$ for $j\in[k]$. If
$k<n$, then $\Sigma^{\prime}$ is a system of blocks of
$Aut(A(n,k,k))|_{\Omega}$ acting on $\Omega$.

Proof It suffices to prove that either $(\Omega^{j})^{g}=\Omega^{j}$ or
$(\Omega^{j})^{g}\cap\Omega^{j}=\emptyset$ for every $g\in Aut(A(n,k,k))$ and
$j\in[k]$. Proof by contradiction. Suppose that there exists an automorphism
$g\in Aut(A(n,k,k))$ such that $(\Omega^{j})^{g}\neq\Omega^{j}$ and
$(\Omega^{j})^{g}\cap\Omega^{j}\neq\emptyset$ for some $j$. Therefore, there
exist $a,b,c,d,i$ such that $(\Delta_{aj})^{g}=\Delta_{bj}$ and
$(\Delta_{cj})^{g}=\Delta_{di}$ and $i\neq j$ and $a\neq c$.

Since $a\neq c$, we deduce that $\Delta_{aj}\cap\Delta_{cj}=\emptyset$.
Therefore, $\Delta_{bj}\cap\Delta_{di}=\emptyset$, and thus $b=d$. Moreover,
$k<n$ indicates that we can pick $[s_{1},...,s_{j-1},a,s_{j+1},...,s_{k}]$ and
$[s_{1},...,s_{j-1},c,s_{j+1},...,s_{k}]$ in $\Delta_{aj}$ and $\Delta_{cj}$
respectively. Suppose
$[s_{1},...,s_{j-1},a,s_{j+1},...,s_{k}]^{g}=[t_{1},...,t_{j-1},b,t_{j+1},...,t_{k}]$
and
$[s_{1},...,s_{j-1},c,s_{j+1},...,s_{k}]^{g}=[r_{1},...,r_{i-1},d,r_{i+1},...,r_{k}]$.
Proceeding as in the proof of Proposition 2.4, we deduce that
$\Sigma^{\prime}$ is also a system of blocks of $Aut(A(n,k,k))|_{\Omega}$
acting on $\Omega$. $\Box$

######  Lemma 2.6.

If $n>k\geq 1$, then $Aut(A(n,k,k))\cong P(S_{n})\times Q(S_{k})$.

Proof Clearly, this lemma holds for $k=1$. Suppose that $n>k>1$. It follows
from Proposition 2.4 that $\Sigma$ is a system of blocks of
$Aut(A(n,k,k))|_{\Omega}$ acting on $\Omega$. Therefore,
$Aut(A(n,k,k))|_{\Omega}$ induces a permutation group acting on $\Sigma$,
denoted by $(Aut(A(n,k,k))|_{\Omega})|_{\Sigma}$. It is obvious that
$(Aut(A(n,k,k))|_{\Omega})|_{\Sigma}\cong S_{n}$. Consider the natural
surjective homomorphism

$\mu:Aut(A(n,k,k))|_{\Omega}\rightarrow(Aut(A(n,k,k))|_{\Omega})|_{\Sigma}.$

It follows from Proposition 2.5 that $ker\mu\cong S_{k}$. So far, we have seen
that

$Aut(A(n,k,k))|_{\Omega}/S_{k}\cong S_{n}.$

Moreover, $P(S_{n})\times Q(S_{k})\leq Aut(A(n,k,k))$ and Proposition 2.3
imply that

$Aut(A(n,k,k))\cong P(S_{n})\times Q(S_{k}).$

This completes the proof of this lemma. $\Box$

Next we consider $A(n,n,n)$ and $A(n,n,2)$. Recall some notions and notations
about Cayley graph. Given a group $G$ and a subset $S\subseteq G$ such that
$1\not\in S$ and $S^{-1}=S$. The Cayley graph of $G$ with respect to the $S$,
denoted by $Cay(G,S)$, is defined to the graph with vertex set $G$ and edge
set $\\{(g,sg)|g\in G,s\in S\\}$. Consider the symmetric group $S_{n}$. If $T$
is the set of all transpositions of $S_{n}$, then $Cay(S_{n},T)$ is called the
complete transposition graph; if $D$ is the set of all derangements of
$S_{n}$, then $Cay(S_{n},D)$ is called the complete derangement graph. Ashwin
Ganesan [11], Yun-Ping Deng and Xiao-Dong Zhang [6] characterized the full
automorphism groups of $Cay(S_{n},T)$ and $Cay(S_{n},D)$ respectively. Next,
we shall prove that $Cay(S_{n},T)\cong A(n,n,2)$ and $Cay(S_{n},D)\cong
A(n,n,n)$.

######  Proposition 2.7.

$Cay(S_{n},T)\cong A(n,n,2)$ and $Cay(S_{n},D)\cong A(n,n,n)$ for all $n>2$.

Proof Defining the mapping $\psi:[n]^{(n)}\rightarrow S_{n}$ under the rule
$\psi([s_{1},s_{2},...,s_{n}])=s_{1}s_{2}\cdot\cdot\cdot s_{n}$ for every
$n$-tuple $[s_{1},s_{2},...,s_{n}]\in[n]^{(n)}$, where
$s_{1}s_{2}\cdot\cdot\cdot s_{n}$ is the permutation that maps $i$ to $s_{i}$
for $i=1,2,...,n$. Clearly, $\psi$ is a bijection between $[n]^{(n)}$ and
$S_{n}$. Next we prove that $\psi$ is not only an isomorphism between
$Cay(S_{n},T)$ and $A(n,n,2)$, but also an isomorphism between $Cay(S_{n},D)$
and $A(n,n,n)$.

Consider $Cay(S_{n},T)$ and $A(n,n,2)$. Let $[s_{1},s_{2},...,s_{n}]$ and
$[t_{1},t_{2},...,t_{n}]$ be two vertices of $A(n,n,2)$. We see that
$\psi([s_{1},s_{2},...,s_{n}])=s_{1}s_{2}\cdot\cdot\cdot s_{n}$ and
$\psi([t_{1},t_{2},...,t_{n}])=t_{1}t_{2}\cdot\cdot\cdot t_{n}$. By definition
of Cayley graph, we know that $\psi([s_{1},s_{2},...,s_{n}])$ and
$\psi([t_{1},t_{2},...,t_{n}])$ are adjacent if and only if
$\psi([s_{1},s_{2},...,s_{n}])\psi([t_{1},t_{2},...,t_{n}])^{-1}\in T$, where
$\psi([t_{1},t_{2},...,t_{n}])^{-1}$ stands for the inverse of
$\psi([t_{1},t_{2},...,t_{n}])$. One easily checks that
$\psi([s_{1},s_{2},...,s_{n}])\psi([t_{1},t_{2},...,t_{n}])^{-1}\in T$ if and
only if $|\\{i|s_{i}\neq t_{i},1\leq i\leq n\\}|=2$. Thereby,
$Cay(S_{n},T)\cong A(n,n,2)$ for all $n>2$. By the same token, we derive
$Cay(S_{n},D)\cong A(n,n,n)$ for all $n>2$. The proof of this proposition is
complete. $\Box$

######  Lemma 2.8.

$Aut(A(n,n,2))\cong[P(S_{n})\times Q(S_{n})]\rtimes Z_{2}$ and
$Aut(A(n,n,n))\cong[P(S_{n})\times Q(S_{n})]\rtimes Z_{2}$ for all $n>2$.
Here, $Z_{2}=\langle h\rangle$ and $h$ is the map that
$[s_{1},s_{2},...,s_{n}]^{h}=[x_{1},x_{2},...,x_{n}]$ where $x_{j}=i$ if
$s_{i}=j$ for $j=1,2,...,n$.

Proof Apply Proposition 2.7 and [11, Theorem 1.1] and [6, Theorem 1.1], we
deduce that both the orders of $Aut(A(n,n,2))$ and $Aut(A(n,n,n))$ are
$2n!n!$. Moreover, $P(S_{n})\times Q(S_{n})\leq Aut(A(n,n,2))$ and
$P(S_{n})\times Q(S_{n})\leq Aut(A(n,n,n))$. So it suffices to prove that $h$
is an automorphism of order $2$ that is not in $P(S_{n})\times Q(S_{n})$.
Clearly, $\psi([s_{1},s_{2},...,s_{n}]^{h})$ is the inverse of
$\psi([s_{1},s_{2},...,s_{n}])$. By Proposition 2.7 and [11, Theorem 1.1] and
[6, Theorem 1.1], $h$ is an automorphism of $Aut(A(n,n,2))$ and
$Aut(A(n,n,n))$ with order $2$. On the other hand, it is easy to see that
$\Sigma$ and $\Sigma^{\prime}$ are two systems of blocks of $P(S_{n})\times
Q(S_{n})|_{\Omega}$ acting on $\Omega$. However, it is easy to check that
$\Sigma$ and $\Sigma^{\prime}$ are not systems of blocks of $\langle
h\rangle|_{\Omega}$ acting on $\Omega$. This completes the proof of this
lemma. $\Box$

So far, we have arrived at Theorem 1.2 by Lemma 2.6 and Lemma 2.8.

##  3 Concluding Remarks

Note that the transposition of $S_{n}$ has $(n-2)$ fixed points, and
derangement of $S_{n}$ has no fixed point. Thereby, we see that the
transposition and derangement have the numbers of fixed points in exactly two
extreme cases. However, $Aut(Cay(S_{n},T))\cong Aut(Cay(S_{n},D))$. So we
propose a bold conjecture that is a generalization of the complete
transposition graph and derangement graph.

######  Conjecture 3.1.

Let $F_{k}$ denotes the set of permutations in $S_{n}$ which have $k$ fixed
points with $0\leq k\leq n-2$. Then
$Aut(Cay(S_{n},F_{k}))\cong[R(S_{n})\rtimes Inn(S_{n})]\rtimes Z_{2}$ for all
$n>2$. Here, $R(S_{n})$ and $Inn(S_{n})$ are the right regular representation
and the inner automorphism group of $S_{n}$ respectively, and $Z_{2}=\langle
h\rangle$ with the mapping $h:g^{h}=h^{-1},\forall g\in S_{n}$.

By the proof of Proposition 2.7, we can infer that $Cay(S_{n},F_{k})\cong
A(n,n,n-k)$. In addition, the maximum independent set of $A(n,k,r)$ becomes
complicated when $r<k$, however, the Question 1.1 may be resolved from the
perspective of maximum clique. So it seems that continuing to investigate
Question 1.1 is more suitable for confirming Conjecture 3.1.

##  References

  * [1] S. B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38 (1989), no. 4, 555-566.
  * [2] P.J. Cameron, Permutation groups, London Mathematical Society Student Texts, vol. 45, Cambridge University Press, Cambridge, 1999.
  * [3] B.F. Chen, E. Ghorbani and K.B. Wong, On the eigenvalues of certain Cayley graphs and arrangement graphs , Linear Algebra Appl., 444 (2014), 246-253.
  * [4] E. Cheng, L. Lipták and A. Yuan, Linearly many faults in arrangement graphs, Networks, 61 (2013), 281-289.
  * [5] K. Day and A. Tripathi, Arrangement graphs: A class of generalized star graphs, Inform. Process. Lett, 42 (1992), 235-241.
  * [6] Yun-Ping Deng and Xiao-Dong Zhang, Automorphism group of the derangement graph, Electron. J. Comb., 18 (2011) #P198.
  * [7] J.D. Dixon and B. Mortimer, Permutation Groups, Graduate Texts in Mathematics, vol. 163, Springer, New York, 1996.
  * [8] Yan-Quan Feng, Automorphism groups of Cayley graphs on symmetric groups with generating transposition sets, J. Combin. Theory Ser. B, 96 (2006), no. 1, 67-72.
  * [9] M. Feng, X. Ma, and K. Wang, The full automorphism group of the power (di)graph of a finite group, European J. Combin., 52 (2016), 197-206.
  * [10] B. Fiona and H. Sophie, Some Erdős-Ko-Rado theorems for injections, European J. Combin., 31 (2010), 839-860.
  * [11] Ashwin Ganesan, Automorphism group of the complete transposition graph, J. Algebr. Comb., 42 (2015), 793-801.
  * [12] C.D. Godsil, On the full automorphism group of a graph, Combinatorica, 1 (1981), no. 3, 243-256.
  * [13] C.D. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, Springer, 2001.
  * [14] H.-C. Hsu, T.-K. Li, J.J.M. Tan and L.-H. Hsu, Fault hamiltonicity and fault hamiltonian connectivity of the Arrangement Graphs, IEEE Trans. Comput., 53 (2004), no. 4, 39-53.
  * [15] P. Klavík, R. Nedela and P. Zeman, Jordan-like characterization of automorphism groups of planar graphs, J. Combin. Theory Ser. B, 157 (2022), 1-39.
  * [16] Junyao Pan, The full automorphism groups of general position graphs, J. Combin. Theory Ser. A, 201 (2024) 105800.
  * [17] Junyao Pan and Xiuyun Guo, The full automorphism groups, determining sets and resolving sets of coprime graphs, Graphs Combin., 35 (2019), no. 2, 485-501.
  * [18] D. Reinhard, Graph Theory, 2nd edn. Springer, New York (1997)
  * [19] P. Torres, The automorphism group of the s-stable Kneser graphs, Adv. in Appl. Math., 89 (2017), 67-75.
  * [20] Fu-Gang Yin, Yan-Quan Feng, Jin-Xin Zhou and Yu-Hong Guo, The symmetry property of $(n,k)$-arrangement graph, J. Graph Theory., 98 (2021), 234-254.