ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P2.06
https://doi.org/10.26493/1855-3974.2621.26f
(Also available at http://amc-journal.eu)
Some remarks on the square graph of the
hypercube
Seyed Morteza Mirafzal *
Department of Mathematics, Lorestan University, Khoramabad, Iran
Received 6 May 2021, accepted 26 June 2022, published online 18 November 2022
Abstract
Let Γ = (V,E) be a graph. The square graph Γ2 of the graph Γ is the graph with the
vertex set V (Γ2) = V in which two vertices are adjacent if and only if their distance in
Γ is at most two. The square graph of the hypercube Qn has some interesting properties.
For instance, it is highly symmetric and panconnected. In this paper, we investigate some
algebraic properties of the graph Q2n. In particular, we show that the graph Q
2
n is distance-
transitive. We show that the graph Q2n is an imprimitive distance-transitive graph if and
only if n is an odd integer. Also, we determine the spectrum of the graph Q2n. Finally, we
show that when n > 2 is an even integer, then Q2n is an automorphic graph, that is, Q
2
n is a
distance-transitive primitive graph which is not a complete or a line graph.
Keywords: Square of a graph, distance-transitive graph, hypercube, automorphism group, Johnson
graph, automorphic graph.
Math. Subj. Class. (2020): Primary 05C25, 94C15
1 Introduction
In this paper, a graph Γ = (V,E) is considered as an undirected simple graph where
V = V (Γ) is the vertex-set and E = E(Γ) is the edge-set. For all the terminology and
notation not defined here, we follow [1, 3, 5, 6, 9].
Let Γ = (V,E) be a graph. The square graph Γ2 of the graph Γ is the (simple)
graph with vertex set V in which two vertices are adjacent if and only if their distance in
Γ is at most two. It is easy to see that Aut(Γ) ≤ Aut(Γ2), where Aut(Γ) denotes the
automorphism group of the graph Γ. Thus, if the graph Γ is a vertex-transitive graph, then
Γ2 is a vertex-transitive graph. A graph Γ of order n > 2 is Hamilton-connected if for any
pair of distinct vertices u and v, there is a Hamilton u-v path, namely, there is a u-v path
*The author is thankful to the anonymous reviewers for their valuable comments and suggestions.
E-mail address: smortezamirafzal@yahoo.com (Seyed Morteza Mirafzal)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 23 (2023) #P2.06
of length n − 1. It is clear that if a graph Γ is Hamilton-connected then it is Hamiltonian.
A graph Γ 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) ≤ l ≤ n − 1. Note that if a graph
Γ is panconnected, then it is Hamilton-connected. It is a well known fact that when a
graph Γ is 2-connected, then its square Γ2 is panconnected [4, 7]. Using this fact, and an
algebraic property of Johnson graphs, recently it has been proved that the Johnson graphs
are panconnected [10].
Let n ≥ 2 be an integer. The hypercube Qn is the graph whose vertex-set is {0, 1}n,
where two n-tuples are adjacent if they differ in precisely one coordinate. This graph has
been studied from various aspects by many authors. Some recent works concerning some
algebraic aspects of this graph include [14, 17, 24, 28]. It is a well known fact that the
graph Qn is a distance-transitive graph [1, 3], and hence it is edge-transitive. Now, using a
well known result due to Watkins [27], it follows that the connectivity of Qn is maximal,
that is, n. Like the hypercube Qn, its square, namely, the graph Q2n has some interesting
properties. For instance, when n ≥ 2, then Qn is 2-connected. Now using a known result
due to Chartrand and Fleischner [4, 7], it follows that Q2n is a panconnected graph. Also,
since Qn is vertex-transitive, the graph Q2n is vertex-transitive, as well. Hence Q
2
n is a
regular graph and it is easy to check that its valency is n+
(
n
2
)
=
(
n+1
2
)
. If n = 2, then Q2n is
the complete graph K4. When n = 3, then Q2n is a 6-regular graph with 8 vertices. This
graph is isomorphic with a graph known as the coktail-party graph CP (4) [1]. It can be
shown that when n = 4, then the graph Q2n is a 10-regular graph with 16 vertices, which is
isomorphic to the complement of the graph known as the Clebsch graph [9].
In this paper, we determine the automorphism group of the graph Q2n. Then we show
that Q2n is a distance-transitive graph. This implies that the connectivity of the graph Q
2
n
is maximal, namely, its valency
(
n+1
2
)
. Also, we will see that the graph Q2n is an imprim-
itive distance-transitive graph if and only if n is an odd integer. A graph Γ is called an
automorphic graph, when it is a distance-transitive primitive graph which is not a com-
plete or a line graph [1]. In the last step of the paper, we show that the graph Q2n is an
automorphic graph if and only if n is an even integer.
2 Preliminaries
The graphs Γ1 = (V1, E1) and Γ2 = (V2, E2) are called isomorphic, if there is a bijection
α : V1 −→ V2 such that {a, b} ∈ E1 if and only if {α(a), α(b)} ∈ E2 for all a, b ∈ V1.
In such a case the bijection α is called an isomorphism. An automorphism of a graph Γ
is an isomorphism of Γ with itself. The set of automorphisms of Γ with the operation of
composition of functions is a group called the automorphism group of Γ and denoted by
Aut(Γ).
The group of all permutations of a set V is denoted by Sym(V ) or just Sym(n) when
|V | = n. A permutation group G on V is a subgroup of Sym(V ). In this case we say that
G acts on V . If G acts on V we say that G is transitive on V (or G acts transitively on V )
if given any two elements u and v of V , there is an element β of G such that β(u) = v. If
Γ is a graph with vertex-set V then we can view each automorphism of Γ as a permutation
on V and so Aut(Γ) = G is a permutation group on V .
A graph Γ is called vertex-transitive if Aut(Γ) acts transitively on V (Γ). We say that Γ
is edge-transitive if the group Aut(Γ) acts transitively on the edge set E, namely, for any
{x, y}, {v, w} ∈ E(Γ), there is some π in Aut(Γ), such that π({x, y}) = {v, w}. We say
S. M. Mirafzal: Some remarks on the square graph of the hypercube 3
that Γ is symmetric (or arc-transitive if for all vertices u, v, x, y of Γ such that u and v are
adjacent, and also, x and y are adjacent, there is an automorphism π in Aut(Γ) such that
π(u) = x and π(v) = y. We say that Γ is distance-transitive if for all vertices u, v, x, y of
Γ such that d(u, v) = d(x, y), where d(u, v) denotes the distance between the vertices u
and v in Γ, there is an automorphism π in Aut(Γ) such that π(u) = x and π(v) = y.
A vertex cut of the graph Γ is a subset U of V such that the subgraph Γ − U induced
by the set V − U is either trivial or not connected. The connectivity κ(Γ) of a nontrivial
connected graph Γ is the minimum cardinality of all vertex cuts of Γ. If we denote by δ(Γ)
the minimum degree of Γ, then κ(Γ) ≤ δ(Γ). A graph Γ is called k-connected (for k ∈ N)
if |V (Γ)| > k and Γ − X is connected for every subset X ⊂ V (Γ) with |X| < k. It is
trivial that if a positive integer m is such that m ≤ κ(Γ), then Γ is an m-connected graph.
We have the following fact.
Theorem 2.1 ([27]). If a connected graph Γ is edge-transitive, then κ(Γ) = δ(Γ), where
δ(Γ) is the minimum degree of vertices of Γ.
Let n, k ∈ N with k < n, and let [n] = {1, ..., n}. The Johnson graph J(n, k) is
defined as the graph whose vertex set is V = {v | v ⊆ [n], |v| = k} and two vertices
v,w are adjacent if and only if |v ∩ w| = k − 1. The class of Johnson graphs is a well
known class of distance-transitive graphs [3]. It is an easy task to show that the set of
mappings H = {fθ | θ ∈ Sym([n])}, fθ({x1, ..., xk}) = {θ(x1), ..., θ(xk)}, is a subgroup
of Aut(J(n, k)) [9]. It has been shown that Aut(J(n, k)) ∼= Sym([n]) if n ̸= 2k, and
Aut(J(n, k)) ∼= Sym([n]) × Z2, if n = 2k, where Z2 is the cyclic group of order 2
[3, 13, 18].
Although in most situations it is difficult to determine the automorphism group of a
graph Γ and how it acts on its vertex and edge sets, there are various papers in the literature,
and some of the recent works include [8, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 26, 28].
Let G be any abstract finite group with identity 1, and suppose Ω is a subset of G, with
the properties:
(i) x ∈ Ω =⇒ x−1 ∈ Ω,
(ii) 1 /∈ Ω.
The Cayley graph Γ = Cay(G; Ω) is the (simple) graph whose vertex-set and edge-set are
defined as follows:
V (Γ) = G, E(Γ) = {{g, h} | g−1h ∈ Ω}.
It can be shown that the Cayley graph Γ = Cay(G; Ω) is connected if and only if the set Ω
is a generating set in the group G [1].
The group G is called a semidirect product of N by Q, denoted by G = N ⋊ Q, if G
contains subgroups N and Q such that:
(i) N ⊴G (N is a normal subgroup of G)
(ii) NQ = G; and
(iii) N ∩Q = 1.
4 Ars Math. Contemp. 23 (2023) #P2.06
3 Main results
The hypercube Qn is the graph whose vertex set is {0, 1}n, where two n-tuples are adja-
cent if they differ in precisely one coordinate. It is easy to show that Qn = Cay(Zn2 ;S),
where Z2 is the cyclic group of order 2, and S = {ei | 1 ≤ i ≤ n}, where ei =
(0, ..., 0, 1, 0, ..., 0), with 1 at the ith position. It is easy to show that the set H = {fθ|θ ∈
Sym([n])}, fθ(x1, ..., xn) = (xθ(1), ..., xθ(n)) is a subgroup of the group Aut(Qn). It is
clear that H ∼= Sym([n]). We know that in every Cayley graph Γ = Cay(G;S), the group
Aut(Γ) contains a subgroup isomorphic with the group G. In fact, if x ∈ Zn2 , and we
define the mapping fx(v) = x + v, for every v ∈ V (Qn), then fx is an automorphism of
the hypercube Qn. Hence Zn2 is (isomorphic with) a subgroup of Aut(Qn). It has been
proved that Aut(Qn) = ⟨Zn2 ,Sym([n])⟩ ∼= Zn2 ⋊ Sym([n]) [14]. It is clear that when Γ is
a graph then Aut(Γ) is a subgroup of Aut(Γ2). Thus we have Aut(Qn) ≤ Aut(Q2n). In
the sequel, we wish to show that the graph Q2n is a distance-transitive graph, and for doing
this we need the automorphism group of Q2n. When n = 3, then Q
2
n is isomorphic with the
coktail-party graph CP (4). The complement of this graph is a disjoint union of 4 copies
of K2. Thus Aut(Q23) ∼= Sym([2]) wrI Sym([4]), where I = {1, 2, 3, 4} [3, 22] (for an
acquaintance with the notion of wreath product of groups see [6]). Now it can be checked
that this graph is a distance-transitive graph. Hence, in the sequel we assume that n > 4.
It is easy to see that for the graph Q2n we have, Q
2
n = Cay(Zn2 ;T ), T = S ∪ S1, where
S1 = {ei + ej | i, j ∈ [n], i ̸= j}. Let A = Aut(Q2n) and A0 be the stabilizer subgroup of
the vertex v = 0 in A. Since Q2n is a vertex-transitive graph, then from the orbit-stabilizer
theorem we have |A| = |A0||V (Q2n)| = 2n|A0|. The following lemma determines an
upper bound for |A0|.
Lemma 3.1. Let n > 4 and A = Aut(Q2n). Let A0 be the stabilizer subgroup of the vertex
v = 0. Then |A0| ≤ (n+ 1)!.
Proof. Let Γ = Q2n. We know that Γ = Cay(Zn2 ;T ), T = S ∪ S1, where S = {ei | 1 ≤
i ≤ n} and S1 = {ei + ej | i, j ∈ [n], i ̸= j}. Let f ∈ A0. Then f(T ) = T . Let G
be the subgraph of Γ which is induced by the subset T . Let h = f |T be the restriction
of the mapping f to the subset T . It is clear that h is an automorphism of the graph
G. It is easy to see that the mapping Φ: A0 → Aut(G), which is defined by the rule
Φ(g) = g|T , is a group homomorphism. Thus we have A0ker(Φ) ∼= im(Φ), and hence we
have |A0| = | ker(Φ)|| im(Φ)|. Since im(Φ) is a subgroup of Aut(G), then we have
|A0| ≤ | ker(Φ)||Aut(G)|. If we show that |Aut(G)| ≤ (n+ 1)! and ker(Φ) = {1}, then
the lemma is proved. Hence in the rest of the proof we show that:
(i) |Aut(G)| ≤ (n+ 1)!,
(ii) ker(Φ) = {1}.
(i) We give two proofs for proving this claim. The first is more elementary than the second,
but we need some parts of it in the proof of (ii). The second is based on the automorphism
group of the Johnson graph J(n, k).
Proof 1 of (i). Consider the graph G. In T = V (G), consider the subgraphs induced by
the subsets C0 = S = {ei| 1 ≤ i ≤ n}, Ci = {ei, ei + ej | 1 ≤ j ≤ n, i ̸= j}, 1 ≤ i ≤ n
(we also denote by Ci the subgraph induced by the set Ci ). It is clear that C0 is an n-
clique in the graph G. Note that if ei+ er and ei+ es are two elements of Ci, then we have
S. M. Mirafzal: Some remarks on the square graph of the hypercube 5
(ei + er)− (ei + es) = er + es ∈ T . Hence each Ci is also an n-clique in the graph G. It
can be shown that each Ci, 0 ≤ i ≤ n is a maximal n-clique in G. It is clear that if i ̸= 0,
then C0 ∩ Ci = {ei}. Moreover, if i, j ∈ {1, ..., n} and i ̸= j, then Ci ∩ Cj = {ei + ej}.
Let M be a maximal n-clique in the graph G. It is not hard to show that M = Cj for
some j ∈ {0, 1, ..., n}. If a is an automorphism of the graph G, then a(Cj) is a maximal
n-clique in the graph G. Hence the natural action of a on the set X = {C0, C1, ..., Cn} is
a permutation on X . Let G1 be the graph with the vertex set X in which two vertices v and
w are adjacent if and only if v ∩ w ̸= ∅. Now, it is clear that G1 ∼= Kn+1, the complete
graph on n + 1 vertices, and hence Aut(G1) ∼= Sym(X). Let a ∈ Aut(G) be such that
a(Cj) = Cj , for each j ∈ {0, 1, ..., n}. Noting that C0 ∩Ci = {ei}, i ̸= 0, we deduce that
a(x) = x for every x ∈ C0. Note that the vertex ei + ej is the unique common neighbor of
vertices ei and ej in the graph G which is not in C0. This implies that a(ei+ej) = ei+ej .
Therefore we have a(v) = v for every v ∈ T . Now it is easy to see that the mapping
π : Aut(G) → Aut(G1) defined by the rule π(a) = fa, where fa(Ci) = a(Ci) for every
Ci ∈ X , is an injection and therefore we have (n+ 1)! ≥ |Aut(G)|.
Proof 2 of (i). Consider the graph G. We show that this graph is isomorphic with the
Johnson graph J(n+ 1, 2). We define the mapping
f : V (G) → V (J(n+ 1, 2)),
by the rule:
f(v) =
{
{i, n+ 1}, if v = ei
{i, j}, if v = ei + ej
It is clear that f is a bijection. Let {v, w} be an edge in the graph G. Then we have three
possibilities:
(1) {v, w} = {ei, ej}, (2) {v, w} = {ei, ei + ek}, (3) {v, w} = {ei + ek, ei + ej}.
Now, we have (1) f({v, w}) = {{i, n + 1}, {j, n + 1}}, (2) f({v, w}) = {{i, n +
1}, {i, k}}, (3) f({v, w}) = {{i, k}, {j, k}}. It follows that f is a graph isomorphism.
Hence, Aut(G) ∼= Aut(J(n+1, 2)). Since Aut(J(n+1, 2)) ∼= Sym([n+1]) [3, 13, 18],
then we have Aut(G) ∼= Sym([n+ 1]).
(ii) we now show that ker(Φ) = {1}. Let f ∈ ker(Φ). Then f(0) = 0 and h = f |T
is the identity automorphism of the graph G. Hence f(x) = x for every x ∈ T . Note
that when x ∈ T , then w(x) ∈ {1, 2}, where w(x) is the weight of x, that is, the number
of 1s in the n-tuple x. Let x ∈ V (Γ) and w(x) = m. We show by induction on m, that
f(x) = x. It is clear that when m = 0, 1, 2, then the claim is true. Let the claim be
true when w(x) ≤ m, m ≥ 2. We show that if w(x) = m + 1, then f(x) = x. Let
y = ei1 + ... + eim + eim+1 be a vertex of weight m + 1. Let v = y + eim + eim+1 .
Since W (v) = m − 1, thus f(v) = v. Let N be the subgraph of Γ which is induced by
the set N(v). Since Γ is vertex-transitive, then G ∼= N . Also, since f(v) = v, then the
restriction of f to N(v) is an automorphism of the graph N . In N(v) we define the subsets
M0 = {v + ei| 1 ≤ i ≤ n}, Mi = {v + ei, v + ei + ej | 1 ≤ j ≤ n, j ̸= i}, 1 ≤ i ≤ n. It
can be check that the subgraph induced by each Mi is a maximal n-clique in the graph N .
Also, M0 ∩Mi = {v + ei}. Moreover, v + ei + ej is the unique common neighbor of the
vertices v + ei and v + ej in the graph N which is not in M0. If x ∈ M0, then f(x) = x,
because w(x) ≤ m. This implies that f(Mi) = Mi. Now, by an argument similar to what
6 Ars Math. Contemp. 23 (2023) #P2.06
is done in Proof 1, we can see that f(x) = x for every x ∈ N(v). Since y ∈ N(v), we
have f(y) = y. We now conclude that f is the identity automorphism of Γ. Hence we have
ker(Φ) = {1}.
Theorem 3.2. Let n > 4 and Γ = Q2n be the square of the hypercube Qn. Then we have
Aut(Γ) ∼= Zn2 ⋊ Sym([n+ 1]).
Proof. Let A0 be the stabilizer subgroup of the vertex v = 0 in the group Aut(Γ). We know
from Lemma 3.1, that |A0| ≤ (n+ 1)!. Let T and X = {C0, ..., Cn} be the sets which are
defined in the proof of Lemma 3.1. Note that Zn2 is a vector space over the field Z2 and Ci,
0 ≤ i ≤ n, is a basis for this vector space. Let fi : C0 → Ci be a bijection. We can linearly
extend fi to an automorphism e(fi) of the group Zn2 . It is clear that e(fi) ∈ A0. We
know that every automorphism of the group Zn2 which fixes the set T is an automorphism
of the graph Γ. We can see that when x, y ∈ Ci and x ̸= y then x + y ∈ T . Thus we
have e(fi)(er + es) = e(fi)(er) + e(fi)(es) ∈ T . Hence we have e(fi)(T ) = T . Since
the number of permutations fi is n!, hence the number of automorphisms of e(fi) is n!.
Note that when i ̸= j, then e(fi) ̸= e(fj). Now since 0 ≤ i ≤ n, then we have at least
(n+ 1)(n!) = (n+ 1)! distinct automorphisms in the group A0. Thus by Lemma 3.1, we
have |A0| = (n + 1)!. We saw, in the proof of Lemma 3.1, that A0 is isomorphic with a
subgroup of Sym([n+ 1]). Hence we deduce that A0 ∼= Sym([n+ 1]).
We know, by the orbit-stabilizer theorem, that |V (Γ)||A0| = |Aut(Γ)|. Thus we have
|Aut(Γ)| = 2n[(n+1)!]. For every v ∈ Zn2 , the mapping fv(x) = v+x, for every x ∈ Zn2 ,
is an automorphism of the graph Γ. It is easy to check that L = {fv| v ∈ Zn2} is a subgroup
of Aut(Γ) which is isomorphic with Zn2 . Also it is easy to check that L∩A0 = {1}. Hence
we have |LA0| = |L||A0| = 2n[(n+ 1)!] = |Aut(Γ)|. This implies that Aut(Γ) = LA0.
Also we can see that for every v ∈ Zn2 and every a ∈ A0 we have a−1fva = fa−1(v). Thus
we deduce that L is a normal subgroup of Aut(Γ). We now conclude that
Aut(Γ) ∼= L⋊A0 ∼= Zn2 ⋊ Sym([n+ 1]).
The graph Q2n has some interesting properties. In the next theorem, we show that Q
2
n
is distance-transitive.
Theorem 3.3. Let n ≥ 4 be an integer. Then the graph Q2n is a distance-transitive graph.
Proof. Let v and w be vertices in Q2n. It is easy to check that d(x, y) = ⌈
w(x+y)
2 ⌉. Hence
we have d(x, 0) = ⌈w(x)2 ⌉. Let D be the diameter of Q
2
n. it follows from the first two
sentences that D = ⌈n2 ⌉. Let A0 be the stabilizer subgroup the vertex v = 0 in Aut(Q
2
n).
Since the graph Q2n is a vertex-transitive graph, it is sufficient to show that the action of
A0 on the set Γk is transitive, where Γk is the set of vertices at distance k from the vertex
v = 0. Let x and y be two vertices in Γk. There are two possible cases, that is,
(i) w(x) = w(y) or
(ii) w(x) ̸= w(y).
(i) Let w(x) = w(y). We know that w(x) ∈ {2k, 2k − 1}. Without loss of generality, we
can assume that w(x) = 2k. Let x = ei1 + ... + ei2k and y = ej1 + ... + ej2k . There are
vertices ex1 , ..., exn−2k and ey1 , ..., eyn−2k in Q
2
n such that
{ei1 , ..., ei2k , ex1 , ..., exn−2k} = C0 = {e1, e2, ..., en} = {ej1 , ..., ej2k , ey1 , ..., eyn−2k}.
S. M. Mirafzal: Some remarks on the square graph of the hypercube 7
Let f be the permutation on the set C0 which is defined by the rule, f(eir ) = ejr , 1 ≤ r ≤
2k, and f(exl) = eyl , 1 ≤ l ≤ n − 2k. We now can see that e(f)(x) = y, where e(f) is
the linear extension of f to Zn2 (see the proof of Theorem 3.2).
(ii) Let w(x) ̸= w(y). Without loss of generality we can assume that w(x) = 2k − 1
and w(y) = 2k. Let x = ei1 + ... + ei2k−1 and y = ej1 + ... + ej2k . Note that y =
(ej1 + ej2k) + (ej2 + ej2k) + ... + (ej2k−2 + ej2k) + (ej2k−1 + ej2k). There are vertices
ex1 , ..., exn−2k+1 and ey1 = ej2k , ey2 , ..., eyn−2k+1 in Q
2
n such that
{ei1 , ..., ei2k−1 , ex1 , ..., exn−2k+1} = C0,
{ej1 + ej2k , ej2 + ej2k , ...+ ej2k−2 + ej2k , ej2k−1 + ej2k}∪
{ey1 , ey2 + ej2k , ..., eyn−2k+1 + ej2k} = Cj2k
We now define the bijection g from C0 to Cj2k by the rule g(eir ) = ejr + ej2k , and
g(ex1) = ey1 , g(exi) = eyi + ej2k , i ̸= 1. Let e(g) be the linear extension of g to Zn2 . This
yields that e(g) is an automorphism of the graph Q2n such that e(g)(x) = y.
Theorem 3.3 implies many results. For instance, we now can deduce from it the fol-
lowing corollary, which is important in applied graph theory and interconnection networks.
Corollary 3.4. Let n ≥ 4 be an integer. Then the connectivity of the graph Q2n is maximal,
namely, n+
(
n
2
)
(its valency).
Proof. By Theorem 3.3 the graph Q2n is distance-transitive, then it is edge-transitive. Thus,
it follows from Theorem 2.1, that the connectivity of the graph Q2n is its valency, namely,
n+
(
n
2
)
.
A block B, in the action of a group G on a set X , is a subset of X such that B∩g(B) ∈
{B, ∅}, for each g in G. If G is transitive on X , then we say that the permutation group
(X,G) is primitive if the only blocks are the trivial blocks, that is, those with cardinality 0, 1
or |X|. In the case of an imprimitive permutation group (X,G), the set X is partitioned
into a disjoint union of non-trivial blocks, which are permuted by G. We refer to this
partition as a block system. A graph Γ is said to be primitive or imprimitive according to
the group Aut(Γ) acting on V (Γ) has the corresponding property. In the sequel, we need
the following definition.
Definition 3.5. A graph Γ = (V,E) of diameter D is said to be antipodal if for any
u, v, w ∈ V such that d(u, v) = d(u,w) = D, then we have d(v, w) = D or v = w.
Let Γi(x) denote the set of vertices of Γ at distance i from the vertex x. Let Γ be a
distance-transitive graph. From Definition 3.5 it follows that if ΓD(x) is a singleton set,
then the graph Γ is antipodal. It is easy to see that the hypercube Qn is antipodal, since
every vertex u has a unique vertex at maximum distance from it. Note that this graph is at
the same time bipartite. We have the following fact [1].
Proposition 3.6. A distance-transitive graph Γ of diameter D has a block X = {u} ∪
ΓD(u) if and only if Γ is antipodal, where ΓD(u) is the set of vertices of Γ at distance D
from the vertex u.
Also, we have the following important fact [1].
8 Ars Math. Contemp. 23 (2023) #P2.06
Theorem 3.7. An imprimitive distance-transitive graph is either bipartite or antipodal.
(Both possibilities can occur in the same graph.)
We now can state and prove the following fact concerning the square of the hypercube
Qn.
Corollary 3.8. Let n ≥ 4 be an integer. Then, the square of the hypercube Qn, namely, the
graph Q2n, is an imprimitive distance-transitive graph if and only if n is an odd integer.
Proof. We know from Theorem 3.3, that the graph Γ = Q2n is a distance-transitive graph.
Let n = 2k be an even integer. If D denotes the diameter of Q2n, then D = k. Let
C0 = {e1, ..., en} be the standard basis of the hypercube Qn. Let w = e1 + e2 + ...+ en
and B1 = {w + ei | 1 ≤ i ≤ n}. Consider the vertex u = 0. It is easy to show that
ΓD(u) = {w} ∪B1. Two vertices w and w + e1 are in ΓD(u), but they are not at distance
k = D from each other, since they are adjacent and k > 1. Thus, when n is an even
integer, then the graph Q2n is not antipodal. Since the girth of Q
2
n is 3, then this graph is
not bipartite. Now, Theorem 3.7 implies that the graph Γ = Q2n is not imprimitive.
Now assume that n = 2k + 1 is an odd integer. It is easy to see that D = k + 1 and
ΓD(0) = {w}. Therefore by Proposition 3.6, Γ is antipodal, and hence has the set {0, w}
as a block. We now conclude that, when n is an odd integer, then Q2n is an imprimitive
graph.
Let Γ = (V,E) be a simple connected graph with diameter D. A distance-regular
graph Γ = (V,E), with diameter D, is a regular connected graph of valency k with the
following property. There are positive integers
b0 = k, b1, ..., bD−1; c1 = 1, c2, ..., cD,
such that for each pair (u, v) of vertices satisfying u ∈ Γi(v), we have
(1) the number of vertices in Γi−1(v) adjacent to u is ci, 1 ≤ i ≤ D.
(2) the number of vertices in Γi+1(v) adjacent to u is bi, 0 ≤ i ≤ D − 1.
The intersection array of Γ is i(Γ) = {k, b1, ..., bD−1; 1, c2, ..., cd}.
It is easy to show that if Γ is a distance-transitive graph, then it is distance-regular [1].
Hence, the hypercube Qn, n > 2 is a distance-regular graph. We can verify by an easy
argument that the intersection array of Qn is
{n, n− 1, n− 2, ..., 1; 1, 2, 3, ..., n}.
In other words, for hypercube Qn, we have bi = n− i, ci = i, 1 ≤ i ≤ n− 1, and b0 = n,
cn = n. In the following theorem, we determine the intersection array of the square of the
hypercube Qn [1].
Theorem 3.9. Let n > 3 be an integer and Γ = Q2n be the square of the hypercube Qn.
Let D denote the diameter of Q2n. Then for the intersection array of this graph we have
b0=
(
n+1
2
)
, bi=
(
n−2i+1
2
)
, ci=
(
2i
2
)
, 1 ≤ i ≤ D − 1. Also, cD=
(
n+1
2
)
, when n is an odd
integer and cD=
(
n
2
)
when n is an even integer.
S. M. Mirafzal: Some remarks on the square graph of the hypercube 9
Proof. Since Q2n is a regular graph of valency
(
n+1
2
)
, thus we have b0=
(
n+1
2
)
. Let u be a
vertex in Q2n at distance i from the vertex v = 0. It is easy to check that w(u) = 2i or
w(u) = 2i− 1. This implies that that the diameter of the graph Q2n is D = ⌈n2 ⌉.
Let u be a vertex in Q2n at distance i ≥ 1 from the vertex v = 0, such that i ̸= D.
There are two cases, that is, w(u) = 2i, or w(u) = 2i − 1. Without lose of generality we
can assume that w(u) = 2i. Hence u is of the form u = ej1 + ej2 + ... + ej2i . Now it is
easy to show that if x is a vertex of Q2n adjacent to u and at distance i− 1 from the vertex
v = 0, then x must be of the form x = u+ ek + el, where ek, el ∈ {ej1 , ej2 , ..., ej2i}. It is
clear that the number of such xs is equal to
(
2i
2
)
. Moreover, If x is a vertex of Q2n adjacent
to u and at distance i + 1 from the vertex v = 0, then x must be of the forms x = u + ek
or x = u + ek + el, where ek, el ∈ {e1, e2, ..., en} − {ej1 , ej2 , ..., ej2i}. It is clear that
the number of such xs is equal to
(
n−2i
1
)
+
(
n−2i
2
)
=
(
n−2i+1
2
)
. We now deduce that when
1 ≤ i ≤ D − 1, then ci=
(
2i
2
)
, and bi=
(
n−2i+1
2
)
.
When n is an odd integer, then the vertex u = e1 + e2 + ... + en is the unique vertex
of Q2n at distance D from the vertex v = 0. Thus cD=
(
n+1
2
)
, namely, the valency of u. If
n is an even integer, then ΓD(0) = {u, u+ ei| 1 ≤ i ≤ n} is the set of vertices of Γ = Q2n
at distance D from the vertex v = 0. Now, by a similar argument which is done in the first
section of the proof, it can be shown that cD=
(
n
2
)
.
Remark 3.10. There are distance-regular graphs Γ = (V,E), with the property that
their squares are not distance-regular. For instance, consider the cycle Cn with vertex
set {0, 1, 2, ..., n− 1}. It is well known that Cn is a distance-regular graph of diameter [n2 ]
with the intersection array:
{2, 1, 1, ..., 1, 1; 1, 1, 1, ..., 1, 2} when n is an even integer and,
{2, 1, 1, ..., 1, 1; 1, 1, 1, ..., 1, 1} when n is an odd integer [1].
Now, assume that n ≥ 7. It can be shown by an easy argument that Γ = C2n is not a
distance-regular graph. To see this fact, let v be a vertex in Cn at distance i from the vertex
0, and ci(v) = |Γi−1(0)∩N(v)|. It is easy to show that Γi(0) = {2i,−2i, 2i−1,−2i+1},
and ci(2i) = 1, but ci(2i− 1) = 2.
Remark 3.11. Let n, k ∈ N with k < n, and let [n] = {1, ..., n}. Consider the Johnson
graph J(n, k). It is clear that the order of this graph is
(
n
k
)
. It is easy to check that J(n, k) ∼=
J(n, n − k), hence we assume that 1 ≤ k ≤ n2 . The class of Johnson graphs is one of the
most well known and interesting subclass of distance-regular graphs [3]. It is easy to show
that if v and w are vertices in the Johnson graph J(n, k), then d(v, w) = k−|v∩w|. Thus,
the diameter of the Johnson graph J(n, k) is k. Note that the graph J(n, 1) is the complete
graph Kn and hence it is distance-regular. The diameter of the graph J(n, 2) is 2, hence the
diameter of its square is 1. Thus the graph J2(n, 2) is the complete graph Km, and hence
it is a distance-regular graph (m=
(
n
2
)
). We can show that when k = 3, then the square of
Johnson graph Γ = J(n, k) is a distance-regular graph if and only if n = 6. For checking
this, let v = {1, 2, 3}. Note that the diameter of the graph Γ2 is 2 and a vertex w in Γ2
is at distance 2 from v if and only if |v ∩ w| = 0. Moreover w is at distance 1 from v if
and only if |v ∩ w| ∈ {1, 2}. Hence Γ21(v) = V (Γ) − {v, vc} and Γ22(v) = {vc}, where
vc is the complement of the set v in the set {1, 2, ..., 6}. Thus vc = {4, 5, 6}. Now, it is
clear that b0(v)=
(
3
2
)(
3
1
)
+
(
3
1
)(
3
2
)
=18. Also, for every w ∈ Γ21(v), c1(w) = 1 and b1(w) = 1,
and c2(vc) = |Γ21(v)| = 18. Thus the graph Γ2 = J2(6, 3) is a distance-regular graph
10 Ars Math. Contemp. 23 (2023) #P2.06
with intersection array {18, 1; 1, 18}. But, if n > 6, then the graph Γ2 = J2(n, 3) is not
distance-regular. In fact if n > 6, then for the vertex v = {1, 2, 3}, each of the vertices
u = {1, 2, 4} and w = {1, 4, 5} is in Γ21(v). If x ∈ Γ22(v) is adjacent to u, then 4 ∈ x, and
hence x = {4}∪y, where y ⊂ vc−{4} and |y| = 2. We now can deduce that b1(u)=
(
n−4
2
)
.
On the other hand, if x ∈ Γ22(v) is adjacent to w, then 4 ∈ x and 5 /∈ x, or 5 ∈ x and 4 /∈ x
or 4, 5 ∈ x. Thus, b1(w)=2
(
n−5
2
)
+
(
n−5
1
)
=
(
n−4
2
)
+
(
n−5
2
)
. This implies that when n ≥ 7
then the graph J2(n, 3) cannot be distance-regular.
By a similar argument we we can show that the graph J2(8, 4) is distance-regular, but
if n > 8, then the graph J2(n, 4) is not distance-regular.
Remark 3.12. Let Γ = (V,E) be a graph. Γ is said to be a strongly regular graph with
parameters (n, k, λ, µ), whenever |V | = n, Γ is a regular graph of valency k, every pair of
adjacent vertices of Γ have λ common neighbor(s), and every pair of non-adjacent vertices
of Γ have µ common neighbor(s). It is clear that the diameter of every strongly regular
graph is 2. It is easy to show that if a graph Γ is a distance-regular graph of diameter
2 and order n, with intersection array (b0, b1; c1, c2), then Γ is a strongly regular graph
with parameters (n, b0, b0 − b1 − 1, c2). We know that the diameter of the graph Q2n is
⌈n2 ⌉. Now, it follows from Theorem 3.3, that Q
2
3 is a strongly regular graph with parameter
(8, 6, 4, 6). This graph is known as the coktail-party graph CP (4) [1]. Also, the graph Q24
is a strongly regular graph with parameter (16, 10, 6, 6). We know that when a graph Γ is a
strongly regular graph with parameters (n, k, λ, µ), then its complement is again a strongly
regular graph with parameter (n, n− k − 1, n− 2− 2k + µ, n− 2k + λ) [9]. Hence, the
complement of the graph Q24 is a strongly regular graph with parameter (16, 5, 0, 2). This
graph is known as the Clebsch graph [9] and it is the unique strongly regular graph with
parameters (16, 5, 0, 2). Figure 1 displays a version of the Clebsch graph (the complement
of the graph Q24) in the plane [9].
Figure 1: The Clebsch graph.
S. M. Mirafzal: Some remarks on the square graph of the hypercube 11
4 The spectrum of the square of the hypercube
The square of the hypercube Qn has some further interesting algebraic properties. For
obtaining some of those properties, we need the spectrum of this graph. The spectrum of
Qn is known [1], however we are not aware of a paper showing the spectrum of Q2n. Here
we compute by means of an algebraic and self-contained method the spectrum of Q2n.
Let Γ = (V,E) be a graph with the vertex set {v1, · · · , vn}. Then the adjacency matrix
of Γ is an n× n matrix A = (aij), in which columns and rows are labeled by V and aij is
defined as follow:
aij = A(vi, vj) =
{
1 if vi is adjacent to vj
0 otherwise.
If Ax = λx, x ̸= 0, then λ is an eigenvalue of A, and x is an eigenvector of A corre-
sponding to λ [9]. Let λ1, · · · , λr be eigenvalues of A with multiplicities m1, · · · ,mr,
respectively. The spectrum of the graph Γ is defined as
Spec(Γ) =
{
λ1, λ2, · · · , λr
m1 m2 · · · mr
}
.
When we work with graphs there is an additional refinement. We can suppose that
an eigenvector is a real function f on the vertices. Then if at any vertex v you sum up
the values of f on its neighboring vertices, you should get λ times the values of f at v.
Formally, ∑
w∈N(v)
f(w) = λf(v).
Let G be a finite abelian group (written additively) of order |G| with identity element
0=0G. A character χ of G is a homomorphism from G into the multiplicative group U
of complex numbers of absolute value 1, that is, a mapping from G into U with χ(g1 +
g2) = χ(g1)χ(g2) for all g1, g2 ∈ G. If G is a finite abelian group, then there are integers
n1, · · · , nk, such that G = Zn1 × · · · × Znk . Let S = {s1, · · · , sn} be a non-empty
subset of G such that 0 ̸∈ S and S = −S. Let Γ = Cay(G;S). Assume f : G −→ C∗
is a character where C∗ is the multiplicative group of the complex numbers. If ωij =
e
2πij
ni , 0 ≤ i ≤ k, 1 ≤ j ≤ ni, is an nith root of unitary, then f is of the form f =
f(ω1,··· ,ωk), where f(ω1,··· ,ωk)(x1, · · · , xk) = ω
x1
1 ω
x2
2 · · ·ω
xk
k , for each (x1, x2, ..., xk) ∈
G [12].
If v is a vertex of Γ, then we know that N(v) = {v + s1, · · · , v + sn} is the set of
vertices that are adjacent to v. We now have
∑
w∈N(v)
f(w) =
n∑
i=1
f(v + si) =
n∑
i=1
f(v)f(si) = f(v)(
n∑
i=1
f(si)).
Therefore, if we let λ = λf =
∑
s∈S f(s) then we have
∑
w∈N(v) f(w) = λff(v),
and hence the mapping f is an eigenvector for the Cayley graph Γ with corresponding
eigenvalue λ = λf =
∑
s∈S f(s).
12 Ars Math. Contemp. 23 (2023) #P2.06
Theorem 4.1. Let n > 3 be an integer and Q2n be the square of the hypercube Qn. Then
each of the eigenvalues of Q2n is of the form,
λi =
1
2
n(n+ 1)− 2i(n+ 1) + 2i2,
for 0 ≤ i ≤ ⌊n+12 ⌋. Moreover, the multiplicity of λ0 is 1, the multiplicity of λi is m(λi)=(
n
i
)
+
(
n
n+1−i
)
, for 1 ≤ i ≤ ⌊n+12 ⌋, when n is an even integer, and m(λi)=
(
n
i
)
+
(
n
n+1−i
)
for 1 ≤ i < ⌊n+12 ⌋, when n is an odd integer, with m(λj)=
(
n
j
)
for j = ⌊n+12 ⌋.
Proof. According to what is stated before this theorem, every eigenvector of the graph
Γ = Q2n = Cay(Zn2 ;S) is of the form f = f(ω1,··· ,ωn), where each ωi, 1 ≤ i ≤ n, is a
complex number such that ω2i = 1, namely, ωi ∈ {1,−1}. We now have
λf =
∑
w∈S
f(w) =
n∑
i=1
f(ei) +
n∑
i,j=1, i ̸=j
f(ei + ej)
=
n∑
i=1
f(ei) +
n∑
i,j=1, i ̸=j
f(ei)f(ej).
Note that for every vertex v = (x1, . . . , xn), xi ∈ {0, 1} in Q2n, we have
f(x1, . . . , xn) = f(w1,...,wn)(x1 . . . , xn) = w
x1
1 . . . w
xn
n .
Note that in the computing of the value of wx11 . . . w
xn
n we can ignore wi when wi = 1.
Thus, for ek = (0, . . . , 0, 1, 0 . . . , 0), where 1 is the kth entry, we have;
f(ek) = f(w1,...,wn)(0, . . . , 0, 1, 0, . . . , 0)
= w01 . . . w
1
kw
0
k+1 . . . w
0
n =
{
−1 if wk = −1
1 if wk = 1
Hence, if in the n-tuple (w1, . . . , wn) the number of −1s is i (and therefore the number of
ls is (n− i)), then in the sum
n∑
k=1
f(ek) =
n∑
k=1
f(w1,...,wn)(0, . . . , xk, 0, . . . , 0), xk = 1,
the contribution of −1 is i and the contribution of 1 is n− i. Therefore, we have
n∑
k=1
f(ek) = −i+ (n− i) = n− 2i.
On the other hand, since
(
n∑
k=1
f(ek))
2 =
n∑
k=1
f(ek)
2
+ 2
n∑
i,j=1, i ̸=j
f(ei)f(ej),
therefore, we have
S. M. Mirafzal: Some remarks on the square graph of the hypercube 13
n∑
i,j=1, i ̸=j
f(ei)f(ej) =
1
2
((n− 2i)2 −
n∑
k=1
f(ek)
2
).
Now since
∑n
k=1 f(ek)
2
= n, thus we have
λf =
n∑
i=1
f(ei) +
n∑
i,j=1, i ̸=j
f(ei)f(ej) = (n− 2i) +
1
2
((n− 2i)2 − n)
=
1
2
n+
1
2
n2 − 2ni+ 2i2 − 2i = 1
2
n(n+ 1)− 2i(n+ 1) + 2i2.
Note that f = f(w1,w2,...,wn), and the number of sequences (w1 . . . , wn) in which i entries
are −1 is
(
n
i
)
. If we denote λf by λi, then we deduce that every eigenvalue of the graph
Q2n is of the form
λi =
1
2
n(n+ 1)− 2i(n+ 1) + 2i2, 0 ≤ i ≤ n. (∗∗)
Consider the real function f(x) = 12n(n + 1) − 2x(n + 1) + 2x
2. Then λi = f(i),
i ∈ {0, 1, ..., n}. This function reaches its minimum at x = n+12 . Now by using some
calculus, we can see that f(x) = f(n + 1 − x). Thus, we have λi = f(i) = f(n + 1 −
i) = λn+1−i, 1 ≤ i ≤ n. Now it follows that if n = 2k, then the multiplicity of λi is(
n
i
)
+
(
n
n+1−i
)
, 1 ≤ i ≤ k. Note that when n = 2k + 1, then n+ 1− (k + 1) = k + 1, thus
λn+1−(k+1) = λk+1. Hence if n = 2k + 1, then the multiplicity of λi is
(
n
i
)
+
(
n
n+1−i
)
,
1 ≤ i ≤ k, and the multiplicity of λk+1 is
(
n
k+1
)
. Note that since the graph Q2n is a(
n+1
2
)
-regular graph, hence the multiplicity of λ0=
(
n+1
2
)
= 12 (n+ 1)n is 1.
Let Γ = (V,E) be a graph. The line graph L(Γ) of the graph Γ is constructed by
taking the edges of Γ as vertices of L(Γ), and joining two vertices in L(Γ) whenever the
corresponding edges in Γ have a common vertex. Note that if e = {v, w} is an edge of Γ,
then its degree in the graph L(Γ) is deg(v) + deg(w) − 2. Concerning the eigenvalues of
the line graphs, we have the following fact [1, 9].
Proposition 4.2. If λ is an eigenvalue of a line graph L(Γ), then λ ≥ −2.
Therefore, if λ < −2 is an eigenvalue of a graph graph Γ, then Γ is not a line graph.
A (c, d)-biregular graph is a bipartite graph in which each vertex in one part has degree
c and each vertex in the other part has degree d [25]. It is known and easy to prove that
if the line graph of the graph Γ is regular, then Γ is a regular or a (c, d)-biregular bipartite
graph.
Theorem 4.3. Let n ≥ 4 be an integer and Q2n be the square of the hypercube Qn. Then
Q2n cannot be a line graph.
Proof. Let k = ⌊n2 ⌋. Hence, if n is an even integer, then n = 2k and if n is an odd integer
then n = 2k + 1. It follows from Theorem 4.1, that the smallest eigenvalue of the graph
Q2n is λk, when n is an even integer and λk+1, when n is an odd integer. Now consider the
eigenvalue λk of the graph Q2n in (**) (in the proof of Theorem 4.1). Therefore if n is an
even integer, then we have
λk = k(2k + 1)− 2k(2k + 1) + 2k2 = k(2k + 1− 4k − 2 + 2k) = −k.
14 Ars Math. Contemp. 23 (2023) #P2.06
Moreover if n = 2k + 1, then we have,
λk+1 = (2k + 1)(k + 1)− 2(k + 1)(2k + 2) + 2(k + 1)2
= (k + 1)(2k + 1− 4k − 4 + 2k + 2) = −k − 1.
We now deduce that when n ≥ 5, then λk ≤ −3. Now, it follows from Proposition 4.2,
when n ≥ 5, then the graph Q2n can not be a line graph.
Our argument shows that if λ is an eigenvalue of the graph Q24, then λ ≥ −2, and hence
in this way we can not say anything about our claim.
We now show that Q24 is not a line graph. On the contrary, assume that Q
2
4 is a line graph.
Thus, there is a graph ∆ such that Q24 = L(∆). Since Q
2
4 is a regular graph, hence
(i) ∆ is a regular graph, or
(ii) ∆ is a biregular bipartite graph.
(i) Let ∆ = (V,E) be a t-regular graph of order h. Since Q24 is 10-regular, thus, L(∆) =
Q24 is a 2t−2 = 10-regular graph, and hence t = 6. Therefore we have 16 = |E| = 126h =
3h, which is impossible.
(ii) Let ∆ = (A ∪ B,E) be a (c, d)-biregular bipartite graph such that every vertex in
A (B) is of degree c (d). Hence we have 16 = |E| = c|A| = d|B|. Thus c and d
must divide 16. On the other hand, if e = {a, b} is an edge of ∆, then we must have
deg(a)+deg(b)−2 = 10 = c+d−2. Hence we have c+d = 12. We now can check that
{c, d} = {4, 8}. Without loss of generality, we can assume that d = 8 and c = 4. Hence
we must have |A| ≥ 8. Now since each vertex in A is of degree c = 4, then we must have,
16 = |E| = c|A| = 4|A| ≥ 4× 8 = 32, which is impossible.
Our argument shows that the graph Q24 is also not a line graph.
An automorphic graph is a distance-transitive graph whose automorphism group acts
primitively on its vertices, and not a complete graph or a line graph.
Automorphic graphs are apparently very rare. For instance, there are exactly three cubic
automorphic graphs [1, 2]. It is clear that for n ≥ 3, the graph Q2n is not a complete graph.
We now derive from Corollary 3.8, and Theorem 4.3, the following important result.
Corollary 4.4. Let n ≥ 4 be an integer. Then the square of the hypercube Qn, that is, the
graph Q2n, is an automorphic graph if and only if n is an even integer.
5 Conclusion
In this paper, we proved that the square of the distance-transitive graph Qn, that is, the
graph Q2n, is again a distance-transitive graph (Theorem 3.3). We showed that there are im-
portant classes of distance-transitive graphs (including the cycle Cn, n ≥ 7), such that their
squares are not even distance-regular (and hence are not distance-transitive) (Remark 3.11).
Also, we determined the spectrum of the graph Q2n (Theorem 4.1). Moreover, we showed
that when n > 3 is an even integer, then the graph Q2n is an automorphic graph, that is, a
distance-transitive primitive graph which is not a complete or a line graph (Corollary 4.4).
ORCID iDs
Seyed Morteza Mirafzal https://orcid.org/0000-0002-3545-7022
S. M. Mirafzal: Some remarks on the square graph of the hypercube 15
References
[1] N. Biggs, Algebraic Graph Theory, Camb. Math. Libr., Cambridge University Press,
Cambridge, 2nd edition, 1994, doi:10.1017/cbo9780511608704, https://doi.org/10.
1017/cbo9780511608704.
[2] N. L. Biggs and D. H. Smith, On trivalent graphs, Bull. London Math. Soc. 3 (1971), 155–158,
doi:10.1112/blms/3.2.155, https://doi.org/10.1112/blms/3.2.155.
[3] A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, volume 18,
Springer-Verlag, New York, 1989, doi:10.1007/978-3-642-74341-2, https://doi.org/
10.1007/978-3-642-74341-2.
[4] G. Chartrand, A. M. Hobbs, H. A. Jung, S. F. Kapoor and C. S. J. A. Nash-Williams, The square
of a block is Hamiltonian connected, J. Comb. Theory, Ser. B 16 (1974), 290–292, doi:10.1016/
0095-8956(74)90075-6, https://doi.org/10.1016/0095-8956(74)90075-6.
[5] R. Diestel, Graph Theory (4th ed.), Springer-Verlage, Heildelberg, 2010, doi:10.1007/
978-3-662-53622-3, https://doi.org/10.1007/978-3-662-53622-3.
[6] J. D. Dixon and B. Mortimer, Permutation Groups, volume 163 of Grad. Texts Math.,
Springer-Verlag, New York, 1996, doi:10.1007/978-1-4612-0731-3, https://doi.org/
10.1007/978-1-4612-0731-3.
[7] H. Fleischner, In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connect-
edness and panconnectedness are equivalent concepts, Monatsh. Math. 82 (1976), 125–149,
doi:10.1007/bf01305995, https://doi.org/10.1007/bf01305995.
[8] A. Ganesan, Automorphism group of the complete transposition graph, J. Algebr. Comb.
42 (2015), 793–801, doi:10.1007/s10801-015-0602-5, https://doi.org/10.1007/
s10801-015-0602-5.
[9] C. Godsil and G. Royle, Algebraic Graph Theory, volume 207 of Grad. Texts Math.,
Springer, New York, 2001, doi:10.1007/978-1-4613-0163-9, https://doi.org/10.
1007/978-1-4613-0163-9.
[10] A. Heidari and S. Morteza Mirafzal, Johnson graphs are panconnected, Proc. Indian Acad. Sci.,
Math. Sci. 129 (2019), 5, doi:10.1007/s12044-019-0527-3, id/No 79, https://doi.org/
10.1007/s12044-019-0527-3.
[11] X. Huang and Q. Huang, Automorphism group of the complete alternating group graph, Appl.
Math. Comput. 314 (2017), 58–64, doi:10.1016/j.amc.2017.07.009, https://doi.org/
10.1016/j.amc.2017.07.009.
[12] G. James and M. Liebeck, Representations and Characters of Groups, Camb. Math. Textb.,
Cambridge University Press, Cambridge, 1993, doi:10.1017/cbo9780511814532, https://
doi.org/10.1017/cbo9780511814532.
[13] G. A. Jones and R. Jajcay, Cayley properties of merged Johnson graphs, J. Algebr. Comb.
44 (2016), 1047–1067, doi:10.1007/s10801-016-0699-1, https://doi.org/10.1007/
s10801-016-0699-1.
[14] S. M. Mirafzal, Some other algebraic properties of folded hypercubes., Ars Comb. 124 (2016),
153–159.
[15] S. M. Mirafzal, The automorphism group of the bipartite Kneser graph, Proc. Indian Acad.
Sci., Math. Sci. 129 (2019), 8, doi:10.1007/s12044-019-0477-9, id/No 34, https://doi.
org/10.1007/s12044-019-0477-9.
[16] S. M. Mirafzal, On the automorphism groups of connected bipartite irreducible graphs, Proc.
Indian Acad. Sci., Math. Sci. 130 (2020), 14, doi:10.1007/s12044-020-00589-1, id/No 57,
https://doi.org/10.1007/s12044-020-00589-1.
16 Ars Math. Contemp. 23 (2023) #P2.06
[17] S. M. Mirafzal, Cayley properties of the line graphs induced by consecutive layers of
the hypercube, Bull. Malays. Math. Sci. Soc. (2) 44 (2021), 1309–1326, doi:10.1007/
s40840-020-01009-3, https://doi.org/10.1007/s40840-020-01009-3.
[18] S. M. Mirafzal, A note on the automorphism groups of Johnson graphs, Ars Comb. 154 (2021),
245–255.
[19] S. M. Mirafzal, On the automorphism groups of us-cayley graphs, 2021,
arXiv:1702.02568v4 [math.CO].
[20] S. M. Mirafzal, The automorphism group of the Andrásfai graph, Discrete Math. Lett. 10
(2022), 60–63.
[21] S. M. Mirafzal and M. Ziaee, Some algebraic aspects of enhanced Johnson graphs, Acta Math.
Univ. Comen., New Ser. 88 (2019), 257–266, www.iam.fmph.uniba.sk/amuc/ojs/
index.php/amuc/article/view/989.
[22] S. M. Mirafzal and M. Ziaee, A note on the automorphism group of the Hamming graph, Trans.
Comb. 10 (2021), 129–136, doi:10.22108/toc.2021.127225.1817, https://doi.org/10.
22108/toc.2021.127225.1817.
[23] S. Morteza Mirafzal, More odd graph theory from another point of view, Discrete Math.
341 (2018), 217–220, doi:10.1016/j.disc.2017.08.032, https://doi.org/10.1016/j.
disc.2017.08.032.
[24] S. Morteza Mirafzal, A new class of integral graphs constructed from the hypercube, Linear
Algebra Appl. 558 (2018), 186–194, doi:10.1016/j.laa.2018.08.027, https://doi.org/
10.1016/j.laa.2018.08.027.
[25] E. R. Scheinerman and D. H. Ullman, Fractional Graph Theory, John Wiley & Sons, Wiley,
1997.
[26] Y. Wang and Y.-Q. Feng, Half-arc-transitive graphs of prime-cube order of small valencies,
Ars Math. Contemp. 13 (2017), 343–353, doi:10.26493/1855-3974.964.594, https://doi.
org/10.26493/1855-3974.964.594.
[27] M. E. Watkins, Connectivity of transitive graphs, J. Comb. Theory 8 (1970), 23–29, doi:
10.1016/s0021-9800(70)80005-9, https://doi.org/10.1016/s0021-9800(70)
80005-9.
[28] J.-X. Zhou, J. H. Kwak, Y.-Q. Feng and Z.-L. Wu, Automorphism group of the balanced hy-
percube, Ars Math. Contemp. 12 (2017), 145–154, doi:10.26493/1855-3974.825.a76, https:
//doi.org/10.26493/1855-3974.825.a76.