45mm45mm40mm50mm

# Symmetric properties and two variants of shuffle-cubes††thanks: This
research was partially supported by NSFC (Nos. 11801061 and 12161002).

Huazhong Lü1 and Kai Deng2
1School of Mathematical Sciences,
University of Electronic Science and Technology of China,
Chengdu, 610054, P.R. China
E-mail<EMAIL_ADDRESS>
2School of Mathematics and Information Science, North Minzu University,
Yinchuan, 750027, P.R. China
E-mail<EMAIL_ADDRESS>
Corresponding author.

###### Abstract

Li et al. in [Inf. Process. Lett. 77 (2001) 35–41] proposed the shuffle cube
$SQ_{n}$ as an attractive interconnection network topology for massive
parallel and distributed systems. By far, symmetric properties of the shuffle
cube remains unknown. In this paper, we show that $SQ_{n}$ is not vertex-
transitive for all $n>2$, which is not an appealing property in
interconnection networks. To overcome this limitation, two novel vertex-
transitive variants of the shuffle-cube, namely simplified shuffle-cube
$SSQ_{n}$ and balanced shuffle cube $BSQ_{n}$ are introduced. Then, routing
algorithms of $SSQ_{n}$ and $BSQ_{n}$ for all $n>2$ are given respectively.
Furthermore, we show that both $SSQ_{n}$ and $BSQ_{n}$ possess Hamiltonian
cycle embedding for all $n>2$. Finally, as a by-product, we mend a flaw in the
Property 3 in [IEEE Trans. Comput. 46 (1997) 484–490].

Key words: Interconnection network; Shuffle-cube; Vertex-transitive;
Simplified shuffle-cube; Balanced shuffle-cube

Mathematics Subject Classification: 05C60, 68R10

##  1\. Introduction

In massive processing systems (MPS), processors are connected based on a
specific interconnection network topology, which is usually represented by an
undirected graph: vertices represent processors and edges represent links
between processors. It is well-known that the network topology plays a crucial
role in its performance. The well-known hypercube (or $n$-cube), which has
received much attention over past decades, is one of the most popular
topologies for MPS. The hypercube possesses numerous desirable properties for
MPS, such as large bandwidth, short (logarithmic) diameter, high symmetry and
connectivity, recursive structure, simple routing and broadcasting. With so
many advantages, a number of hypercube machines have been implemented [14],
such as Cosmic Cube [30], the Ametek S/14 [6], the iPSC [12], the NCUBE [27],
and the CM-200 [9].

However, a network topology can not be optimum in all aspects. To enhance some
properties of the hypercube, a number of variations of the hypercube have been
proposed. One method of reducing diameter of the hypercube is to still retain
the “hypercube-like” structure by twisting some pair of edges, such as twisted
cube [1], Möbius cube [10], crossed cube [17] and Mcube [31]. Another feasible
approach is to reduce vertex degree that leads to technological problems in
parallel computing, such as Fibonacci cube [16], Lucas cube [26] and exchanged
hypercube [25]. In addition, other pleasing hypercube variants are obtained by
adopting different techniques, such as balanced hypercube [32], folded
hypercube [13], generalized hypercube [7] and shuffle-cube [20]. The shuffle-
cube $SQ_{n}$ has some good combinatorial properties and fault-tolerant
properties. The reliability of the shuffle cube concerning refined
connectivity were determined in [33, 29, 11]. The conditional diagnosability
of $SQ_{n}$ was studied in [34, 23]. The matching preclusion number was
determined by Antantapantula et al. [4]. Fault-tolerant Hamiltonian cycle
embedding of the shuffle-cube was investigated by Li et al. [21].

To achieve high performance, graphs with high levels of symmetry (e.g., Cayley
graphs [2, 19]) are recommended as network topologies since it often
simplifies the computation and routing algorithms. Actually, vertex-transitive
and/or edge-transitive graphs are widely used to design networks of high
levels of symmetry. For example, numerous attractive networks, including
hypercube, $k$-ary $n$-cube, balanced hypercube, folded hypercube, star graphs
and some of their variants, which have both theoretical and practical
importance, are vertex-transitive and/or edge-transitive. On the other hand,
to study the symmetry of a graph, the aim is to obtain as much information as
possible about its symmetric property.

Routing is the problem of finding path between each pair of vertices in a
graph. It is well-known that a good routing algorithm does not require large
amount of memory resources to build the routing table, and its convergence
time is usually slow for large networks. Because of the importance of a good
routing in interconnection networks, it has received considerable attention in
the literature [22, 24, 18, 35]. In particular, a path/cycle consisting of all
nodes of a network, i.e. Hamiltonian path/cycle, has a wide range of
importance in theory and practice since there are some applications of
Hamiltonian path in the on-line optimization of a complex Flexible
Manufacturing System [5], as well as full utilization of all nodes in a
network [28].

The rest of this paper is organized as follows. In Section 2, some notations
and the definition of the shuffle-cube are presented. In Section 3, it is
showed that the shuffle-cube is neither vertex-transitive nor edge-transitive.
In Section 4, two vertex-transitive variants of the shuffle cube are proposed.
The routing algorithms and Hamiltonian cycle embeddings of the variants are
investigated in Section 5 and 6, respectively. Conclusions are given in
Section 7.

##  2\. Preliminaries

Let $G=(V(G),E(G))$ be a graph, where $V(G)$ is the vertex-set of $G$ and
$E(G)$ is the edge-set of $G$. The number of vertices of $G$ is denoted by
$|G|$. A path $P=\langle x_{0},x_{1},\cdots,x_{k}\rangle$ in $G$ is a sequence
of distinct vertices so that there is an edge joining each pair of consecutive
vertices. If a path $C=\langle x_{0},x_{1},\cdots,x_{k}\rangle$ is such that
$k\geq 3$, $x_{0}=x_{k}$, then $C$ is said to be a cycle, and the length of
$C$ is the number of edges contained in $C$. The length of the shortest cycle
of $G$ is called the girth of $G$, denoted by $g(G)$. In particular, a cycle
containing all vertices of $G$ is called a Hamiltonian cycle. The clique of
$G$ is a set of pairwise adjacent vertices and the clique number of $G$, is
the maximum size of a clique in $G$. A graph $G$ is vertex-transitive if for
each pair $u,v\in V(G)$ there exists an automorphism that maps $u$ to $v$. A
graph $G$ is edge-transitive if for all $e,f\in E(G)$ there exists an
automorphism of $G$ that maps the endpoints of $e$ to the endpoints of $f$.
For other standard graph notations not defined here please refer to [8].

The vertices are labelled by binary sequences of $n$-bit. For a vertex
$u=u_{n-1}u_{n-2}$ $\cdots u_{1}u_{0}$, $u_{i}\in\\{0,1\\}$ for each $0\leq
i\leq n-1$, the $j$-prefix of $u$ is $u_{n-1}u_{n-2}\cdots$ $u_{n-j}$, written
by $p_{j}(u)$, and the $k$-suffix of $u$ is $u_{k-1}u_{k-2}\cdots u_{1}u_{0}$,
written by $s_{k}(u)$. The Hamming distance of two vertices $u$ and $v$,
denoted by $h(u,v)$, is the number of bits which they differ. The well-known
$n$-dimensional hypercube $Q_{n}$, consists of all of the $n$-bit binary
sequences as its vertex set and two distinct vertices $u$ and $v$ are linked
by an edge if and only if $h(u,v)=1$.

To recursively build shuffle-cubes, we define four sets containing $4$-tuple
of binary sequences as follows:

  * •

$V_{00}=\\{1111,0001,0010,0011\\}$,

  * •

$V_{01}=\\{0100,0101,0110,0111\\}$,

  * •

$V_{10}=\\{1000,1001,1010,1011\\}$,

  * •

$V_{11}=\\{1100,1101,1110,1111\\}$.

We are ready to give the definition of the shuffle-cube.

###### Definition 1

.[20] The $n$-dimensional shuffle-cube, $SQ_{n}$, is recursively defined as
follows: $SQ_{2}\cong Q_{2}$. For $n\geq 3$, $SQ_{n}$ contains exactly 16
subcubes $SQ_{n-4}^{i_{1}i_{2}i_{3}i_{4}}$, where
$i_{1},i_{2},i_{3},i_{4}\in\\{0,1\\}$ and all vertices of
$SQ_{n-4}^{i_{1}i_{2}i_{3}i_{4}}$ share the same
$p_{4}(u)=i_{1}i_{2}i_{3}i_{4}$. The vertices $u=u_{n-1}u_{n-2}\cdots
u_{1}u_{0}$ and $v=v_{n-1}v_{n-2}\cdots v_{1}v_{0}$ in different subcubes of
dimension $n-4$ are adjacent in $SQ_{n}$ iff

  1. (1).

$s_{n-4}(u)=s_{n-4}(v)$, and

  2. (2).

$p_{4}(u)\oplus p_{4}(v)\in V_{s_{2}(u)}$,

where the notation “$\oplus$” means bitwise addition under modulo 2.

By the definition above, it is clear that $SQ_{n}$ is $n$-regular and
$|V(SQ_{n})|=2^{n}$, which is the same as that of $Q_{n}$. For clarity,
$SQ_{6}$ is illustrated in Fig. 1 with only edges incident to vertices in
$SQ_{2}^{0000}$.

By Definition 1, it implies that two vertices in different subcubes of
dimension $n-4$ differ in exactly one 4-bit. For convenience, the $j$-th 4-bit
of a vertex $u$, denoted by $u_{4}^{j}$, is defined as
$u_{4}^{j}=u_{4j+1}u_{4j}u_{4j-1}u_{4j-2}$, $1\leq j\leq\frac{n-2}{4}$. For
notation consistency, we define $u_{4}^{0}=u_{1}u_{0}$. For two distinct
vertices $u$ and $v$ in $SQ_{n}$, $u_{4}^{j}=v_{4}^{j}$ if they bitwise equal.
The complementary of an arbitrary bit $u_{i}$ of $u$, i.e. $1-u_{i}$, is
denoted by $\overline{u}_{i}$. Similar to Hamming distance, we define 4-bit
Hamming distance between $u$ and $v$, written by $h_{4}(u,v)$, as the number
of 4-bits $u^{j}_{4}$ with $0\leq j\leq\frac{n-2}{4}$ such that $u^{j}_{4}\neq
v^{j}_{4}$. In particular, we use $h^{*}_{4}(u,v)$ to denote the number of
4-bits $u^{j}_{4}$ with $1\leq j\leq\frac{n-2}{4}$ such that $u^{j}_{4}\neq
v^{j}_{4}$.

Fig. 1: $SQ_{6}$.

##  3\. Symmetric properties of shuffle-cubes

In this section, we shall state some symmetric properties of shuffle-cubes. We
begin with the following lemma.

###### Lemma 1

. $SQ_{n}$ is non-bipartite for all $n>2$. Moreover, $g(SQ_{n})=3$ for all
$n>2$.

Proof. To show that $SQ_{n}$ is non-bipartite for all $n>2$, it suffices to
present an odd cycle of $SQ_{n}$. Let $u=u_{n-1}u_{n-2}\cdots u_{1}u_{0}$ be a
vertex in $SQ_{n}$ with $u_{4}^{0}=u_{1}u_{0}=00$ and let $v,w,x$ and $y$ be
four neighbors of $u$ with $u_{4}^{j}\neq
v_{4}^{j},w_{4}^{j},x_{4}^{j},y_{4}^{j}$ for some $1\leq j\leq\frac{n-2}{4}$.
It follows that $v_{4}^{0}=w_{4}^{0}=x_{4}^{0}=y_{4}^{0}=00$.

Additionally, we may assume that
$u_{4j+1}u_{4j}=v_{4j+1}v_{4j}=w_{4j+1}w_{4j}=x_{4j+1}x_{4j}$ and
$y_{4j+1}y_{4j}=\bar{u}_{4j+1}\bar{u}_{4j}$. It follows from Definition 1 that
$u,v,w$ and $x$ are pairwise adjacent, forming a clique of size four.
Moreover, $y$ is not adjacent to none of $v,w$ and $x$. Suppose that there
exists another vertex $z$ ($\neq y$) such that $z$ is adjacent to all of
$u,v,w$ and $x$. We claim that $z_{4}^{j}\neq
u_{4}^{j},v_{4}^{j},w_{4}^{j},x_{4}^{j}$. Otherwise, suppose without loss of
generality that $z_{4}^{j}=u_{4}^{j}$. Therefore, $z_{4}^{i}\neq u_{4}^{i}$
for some $i\neq j$, $0\leq i\leq\frac{n-2}{4}$. So $z$ and $v$ (resp. $w$,
$x$) differ in two 4-bits, a contradiction. Thus, the claim holds. Note that
$u_{4}^{j}\oplus z_{4}^{j}\in V_{00}$, then
$z_{4}^{j}=\overline{u}_{4j+1}\overline{u}_{4j}\overline{u}_{4j-1}\overline{u}_{4j-2}$.
By Definition 1, $z$ is not adjacent to $v,w$ and $x$, a contradiction again.

This completes the proof. ∎

###### Lemma 2

. A vertex of $u=u_{n-1}u_{n-2}\cdots u_{1}u_{0}$ of $SQ_{n}$ ($n>2$) is
contained in a clique of size four if and only if $u_{4}^{0}=00$. Moreover,
the clique number of $SQ_{n}$ is four.

Proof. It has been shown in the proof of Lemma 1 that if $u_{4}^{0}=00$, there
are four vertices $u,v,w$ and $x$ forming a clique of size four. To prove the
clique number of is four, we show that there exists no vertex adjacent to all
of $u,v,w$ and $x$.

In what follows, we prove the necessity. Suppose on the contrary that
$u_{4}^{0}\neq 00$. We shall prove that any pair of the neighbors of $u$ are
nonadjacent. Let $v$ and $w$ be two arbitrary neighbors of $u$ and let
$u_{4}^{i}\neq v_{4}^{i}$ and $u_{4}^{j}\neq w_{4}^{j}$, where $0\leq
i,j\leq\frac{n-2}{4}$. The following two cases arise.

Case 1: $i\neq j$. This implies that $v$ and $w$ differ in two $4$-bits. By
Definition 1, $v$ and $w$ are nonadjacent.

Case 2: $i=j$. If $i=j=0$, then $v$ and $w$ are in the same $SQ_{2}$ of
$SQ_{n}$. By Definition 1, $v$ and $w$ are nonadjacent. So we assume that
$i=j>0$. Clearly, $u_{4}^{0}=v_{4}^{0}=w_{4}^{0}$. It follows that
$u_{4i+1}u_{4i}\oplus v_{4i+1}v_{4i}=u_{4}^{0}$ and $u_{4i+1}u_{4i}\oplus
w_{4i+1}w_{4i}=u_{4}^{0}$, implying that $v_{4i+1}v_{4i}=w_{4i+1}w_{4i}\neq
u_{4}^{0}$. On the contrary, suppose that $v$ and $w$ are adjacent. Since
$v_{4}^{i}\neq w_{4}^{i}$, we have $v_{4}^{i}\oplus w_{4}^{i}=00xy$, where
$x,y\in\\{0,1\\}$ are two bits we do not care. This contradicts the fact that
the first two bits of $v_{4}^{i}$, $w_{4}^{i}$ are the same as $v_{4}^{0}$.
This completes the proof. ∎

Remark 1. Any vertex $u=u_{n-1}u_{n-2}\cdots u_{1}u_{0}$ of $SQ_{n}$ ($n>2$)
with $u_{1}u_{0}=00$ and its $j$-bit neighbors $v,w$ and $x$ with
$u_{4j+1}u_{4j}=v_{4j+1}v_{4j}=w_{4j+1}w_{4j}=x_{4j+1}x_{4j}$, form a clique
of size four. So $u$ is contained in exactly $\frac{n-2}{4}$ cliques of size
four. Moreover, $SQ_{n}$ consists of $4^{\frac{n-2}{4}}$ vertex-disjoint
clique of size four.

###### Theorem 3

. $SQ_{n}$ is vertex transitive for $n=2$, but not vertex-transitive for all
$n>2$.

Proof. Clearly, $SQ_{2}$ consists of 16 vertex-disjoint 4-cycles, which is
obviously vertex-transitive. By Lemma 2, we know that each vertex $u$ with
$u_{4}^{0}=00$ is contained in a clique of size four in $SQ_{n}$, $n>2$. Any
vertex $v$ with $u_{4}^{0}\neq 00$ is contained in no clique of size four,
showing obviously that $SQ_{n}$ is not vertex-transitive for all $n>2$. ∎

It is well-known that an edge-transitive but not vertex-transitive graph must
be bipartite. Combing Lemma 1 with Theorem 3, we have the following corollary.

###### Corollary 4

. $SQ_{n}$ is not edge-transitive for all $n>2$.

##  4\. Two vertex-transitive variations of the shuffle-cubes

As we have shown in the previous section, the shuffle-cube $SQ_{n}$ ($n>2$) is
not vertex-transitive. In this section, we shall present two variants of the
shuffle-cubes, which are both vertex-transitive. We shall adopt the notations
which we have defined in the $SQ_{n}$.

###### Definition 2

. The $n$-dimensional simplified shuffle cube, $SSQ_{n}$, is recursively
defined as follows: $SSQ_{2}\cong Q_{2}$. For $n>2$, $SSQ_{n}$ contains
exactly 8 subcubes $SSQ_{n-4}^{i_{1}i_{2}i_{3}i_{4}}$, where
$i_{1}i_{2}\in\\{00,11\\}$, $i_{3},i_{4}\in\\{0,1\\}$ and all vertices of
$SSQ_{n-4}^{i_{1}i_{2}i_{3}i_{4}}$ share the same
$p_{4}(u)=i_{1}i_{2}i_{3}i_{4}$. The vertices $u=u_{n-1}u_{n-2}\cdots
u_{1}u_{0}$ and $v=v_{n-1}v_{n-2}\cdots v_{1}v_{0}$ in different subcubes of
dimension $n-4$ are adjacent in $SSQ_{n}$ iff

  1. (1).

$s_{n-4}(u)=s_{n-4}(v)$, and

  2. (2).

$p_{4}(u)\oplus p_{4}(v)\in V_{00}$,

where the notation “$\oplus$” means bitwise addition under modulo 2.

The reason why we define $i_{1}i_{2}\in\\{00,11\\}$ (which is slightly
different from the definition of $SQ_{n}$) is that if we define
$i_{1},i_{2}\in\\{0,1\\}$ as in Definition 1, then the resulting graph is
always disconnected, which does not meet the basic requirement of
interconnection networks. As a result, $SSQ_{n}$ has $2^{\frac{3n+2}{4}}$
vertices, $n\equiv 2(\text{mod}\ 4)$. Clearly, $SSQ_{n}$ is also $n$-regular
and non-bipartite. $SSQ_{6}$ is illustrated in Fig. 2 with only edges incident
to vertices in $SSQ_{2}^{0000}$.

Fig. 2: $SSQ_{6}$.

In what follows, we shall prove the vertex-transitivity of $SSQ_{n}$, $n\geq
2$.

###### Theorem 5

. $SSQ_{n}$ is vertex-transitive whenever $n\geq 2$.

Proof. Obviously, $SSQ_{n}$ is vertex-transitive if $n=2$. It suffices to show
that $SSQ_{n}$ is vertex-transitive for $n>2$.

Let $u=u_{n-1}u_{n-2}\cdots u_{1}u_{0}$ and $v=v_{n-1}v_{n-2}\cdots
v_{1}v_{0}$ be any two distinct vertices of $SSQ_{n}$. Our objective is to
show that there is an automorphism $\phi$ of $SSQ_{n}$ such that $\phi(v)=u$.
Thus, for any vertex $w=w_{n-1}w_{n-2}\cdots w_{1}w_{0}$ of $SSQ_{n}$, we
define $\phi$ 4-bit by 4-bit (in fact, $w_{4}^{0}$ contains exactly two bits)
below:

$\phi(w_{4}^{j})=w_{4}^{j}\oplus(u_{4}^{j}\oplus v_{4}^{j}),\ 0\leq
j\leq\frac{n-2}{4}.$

Now we are ready to show that $\phi$ is an isomorphism of $SSQ_{n}$. Let $xy$
be an arbitrary edge of $SSQ_{n}$. We shall show that $\phi(x)\phi(y)$ is also
an edge of $SSQ_{n}$. By Definition 2, we known that $x=x_{n-1}x_{n-2}\cdots
x_{1}x_{0}$ and $y=y_{n-1}y_{n-2}\cdots y_{1}y_{0}$ differ in exactly one
4-bit (including the last two bits), say $j$, $0\leq j\leq\frac{n-2}{4}$.

If $x_{4}^{0}\neq y_{4}^{0}$, then $x_{1}x_{0}\neq y_{1}y_{0}$ and
$x_{n-1}x_{n-2}\cdots x_{3}=y_{n-1}y_{n-2}\cdots y_{3}$. By the definition of
$\phi$, we have $\phi(x_{4}^{0})=x_{4}^{0}\oplus(u_{4}^{j}\oplus v_{4}^{j})$
and $\phi(y_{4}^{0})=y_{4}^{0}\oplus(u_{4}^{j}\oplus v_{4}^{j})$.
Additionally, $\phi(x_{4}^{j})=\phi(y_{4}^{j})$ for $1\leq
j\leq\frac{n-2}{4}$. Thus, $\phi(x)\phi(y)\in E(SSQ_{n})$.

If $x_{4}^{j}\neq y_{4}^{j}$ for some $j\in\\{1,\cdots,\frac{n-2}{4}\\}$, then
$x_{1}x_{0}=y_{1}y_{0}$ and $x_{4}^{i}=y_{4}^{i}$ for all
$i\in\\{0,\cdots,\frac{n-2}{4}\\}\setminus\\{j\\}$.

By the definition of $\phi$, we have
$\phi(x_{4}^{j})=x_{4}^{j}\oplus(u_{4}^{j}\oplus v_{4}^{j})$ and
$\phi(y_{4}^{j})=y_{4}^{j}\oplus(u_{4}^{j}\oplus v_{4}^{j})$. Additionally,
$\phi(x_{4}^{i})=\phi(y_{4}^{i})$ for all
$i\in\\{0,\cdots,\frac{n-2}{4}\\}\setminus\\{j\\}$. Thus, $\phi(x)\phi(y)\in
E(SSQ_{n})$. This completes the proof.∎

In the following, we shall give another variation of the shuffle cubes, which
is motivated by the idea of construction of the balanced hypercubes [32]. For
the readability of this paper, we first present the definition of the balanced
hypercube, and then give the definition of the balanced shuffle cube.

###### Definition 3

[32]. An $n$-dimensional balanced hypercube $BH_{n}$ contains $4^{n}$ vertices
$(a_{0},$ $\cdots,a_{i-1},$ $a_{i},a_{i+1},\cdots,a_{n-1})$, where
$a_{i}\in\\{0,1,2,3\\}$ $(0\leq i\leq n-1)$. Any vertex
$v=(a_{0},\cdots,a_{i-1},$ $a_{i},a_{i+1},\cdots,a_{n-1})$ in $BH_{n}$ has the
following $2n$ neighbors:

  1. (1).

$((a_{0}+1)$ mod $4,a_{1},\cdots,a_{i-1},a_{i},a_{i+1},\cdots,a_{n-1})$,
$((a_{0}-1)$ mod $4,a_{1},\cdots,a_{i-1},a_{i},a_{i+1},\cdots,a_{n-1})$, and

  2. (2).

$((a_{0}+1)$ mod $4,a_{1},\cdots,a_{i-1},(a_{i}+(-1)^{a_{0}})$ mod
$4,a_{i+1},\cdots,a_{n-1})$,
$((a_{0}-1)$ mod $4,a_{1},\cdots,a_{i-1},(a_{i}+(-1)^{a_{0}})$ mod
$4,a_{i+1},\cdots,a_{n-1})$.

###### Definition 4

. The $n$-dimensional balanced shuffle cube, $BSQ_{n}$, is recursively defined
as follows: $BSQ_{2}\cong Q_{2}$. For $n\geq 3$, $BSQ_{n}$ contains exactly 16
subcubes $BSQ_{n-4}^{i_{1}i_{2}i_{3}i_{4}}$, where
$i_{1},i_{2},i_{3},i_{4}\in\\{0,1\\}$ and all vertices of
$BSQ_{n-4}^{i_{1}i_{2}i_{3}i_{4}}$ share the same
$p_{4}(u)=i_{1}i_{2}i_{3}i_{4}$. The vertices $u=u_{n-1}u_{n-2}\cdots
u_{1}u_{0}$ and $v=v_{n-1}v_{n-2}\cdots v_{1}v_{0}$ in different subcubes of
dimension $n-4$ are adjacent in $BSQ_{n}$ iff

  1. (1).

$s_{n-4}(u)=s_{n-4}(v)$, and

  2. (2).

$u_{n-2}$ and $v_{n-2}$ have different parities, and
$v_{n-1}v_{n-2}=u_{n-1}u_{n-2}\pm 1$, and

  3. (3).

$v_{n-3}v_{n-4}=u_{n-3}u_{n-4}+(-1)^{u_{n-2}}$, or
$v_{n-3}v_{n-4}=u_{n-3}u_{n-4}$.

where addition and substraction are under modulo 4 by regarding the two bits
as an integer.

Clearly, $BSQ_{n}$ has $2^{n}$ vertices, $n\equiv 2(\text{mod}\ 4)$.
Additionally, $BSQ_{n}$ is $n$-regular and bipartite. $BSQ_{6}$ is illustrated
in Fig. 3 with only edges incident to vertices in $BSQ_{2}^{0000}$.

Fig. 3: $BSQ_{6}$.

We shall prove the following statement, which directly leads to the regularity
of $BSQ_{n}$, $n\geq 2$.

###### Theorem 6

. $BSQ_{n}$ is vertex-transitive whenever $n>2$.

Proof. Clearly, $BSQ_{n}$ is vertex-transitive when $n=2$. It remains to show
that $BSQ_{n}$ is vertex-transitive for $n>2$.

Let $v=v_{n-1}v_{n-2}\cdots v_{1}v_{0}$ and $u=u_{n-1}u_{n-2}\cdots
u_{1}u_{0}$ be any two distinct vertices of $BSQ_{n}$. Our aim is to show that
there is an automorphism $\psi$ of $BSQ_{n}$ such that $\psi(v)=u$. Thus, for
any vertex $w=w_{n-1}w_{n-2}\cdots w_{1}w_{0}$ of $BSQ_{n}$, we define $\psi$
4-bit by 4-bit (in fact, $w_{4}^{0}$ contains exactly two bits) below:
If both of $u_{4j}$ and $v_{4j}$ are even, then

$\psi(w_{4}^{j})=(v_{4j+1}v_{4j}-u_{4j+1}u_{4j}+w_{4j+1}w_{4j},v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}+w_{4j-1}w_{4j-2});$

If $u_{4j}$ is even and $v_{4j}$ is odd, then

$\psi(w_{4}^{j})=(v_{4j+1}v_{4j}-u_{4j+1}u_{4j}-w_{4j+1}w_{4j},v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}-w_{4j-1}w_{4j-2});$

If $u_{4j}$ is odd and $v_{4j}$ is even, then

$\psi(w_{4}^{j})=(-v_{4j+1}v_{4j}+u_{4j+1}u_{4j}-w_{4j+1}w_{4j},-v_{4j-1}v_{4j-2}+u_{4j-1}u_{4j-2}-w_{4j-1}w_{4j-2});$

If both of $u_{4j}$ and $v_{4j}$ are odd, then

$\psi(w_{4}^{j})=(v_{4j+1}v_{4j}-u_{4j+1}u_{4j}+w_{4j+1}w_{4j},v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}+w_{4j-1}w_{4j-2});$

$1\leq j\leq\frac{n-2}{4}$, and addition and substraction are under modulo 4
by regarding the two bits as an integer. In addition,

$\psi(w_{4}^{0})=v_{1}v_{0}+(w_{1}w_{0}-u_{1}u_{0})\ \text{when}\ j=0.$

Let $xy$ be an arbitrary edge of $BSQ_{n}$ with $x=x_{n-1}x_{n-2}\cdots
x_{1}x_{0}$ and $y=y_{n-1}y_{n-2}\cdots y_{1}y_{0}$. We shall show that
$\psi(x)\psi(y)$ is also an edge of $BSQ_{n}$. By Definition 4, it is obvious
that $x$ and $y$ differ in exactly one 4-bit (including the last two bits),
say $j$, $0\leq j\leq\frac{n-2}{4}$.

If $x_{4}^{0}\neq y_{4}^{0}$, then $x_{1}x_{0}\neq y_{1}y_{0}$ and
$x_{n-1}x_{n-2}\cdots x_{3}=y_{n-1}y_{n-2}\cdots y_{3}$. By the definition of
$\psi$, we have $\psi(x_{4}^{0})=v_{1}v_{0}+(x_{1}x_{0}-u_{1}u_{0})$ and
$\phi(y_{4}^{0})=v_{1}v_{0}+(y_{1}y_{0}-u_{1}u_{0})$. Additionally,
$\psi(x_{4}^{j})=\psi(y_{4}^{j})$ for $1\leq j\leq\frac{n-2}{4}$. Thus,
$\psi(x)\psi(y)\in E(BSQ_{n})$.

If $x_{4}^{j}\neq y_{4}^{j}$ for some $j\in\\{1,\cdots,\frac{n-2}{4}\\}$, then
$x_{1}x_{0}=y_{1}y_{0}$ and $x_{4}^{i}=y_{4}^{i}$ for all
$i\in\\{0,\cdots,\frac{n-2}{4}\\}\setminus\\{j\\}$. By the definition of
$\psi$, the following cases arise.

Case 1. $u_{4j}$ is even.

Case 1.1. $v_{4j}$ is even. Clearly, we have
$\psi(x_{4}^{j})=(v_{4j+1}v_{4j}-u_{4j+1}u_{4j}+x_{4j+1}x_{4j},v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}+x_{4j-1}x_{4j-2})$
and
$\psi(y_{4}^{j})=(v_{4j+1}v_{4j}-u_{4j+1}u_{4j}+y_{4j+1}y_{4j},v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}+y_{4j-1}y_{4j-2})$.
Thus, the parity of $v_{4j+1}v_{4j}-u_{4j+1}u_{4j}+x_{4j+1}x_{4j}$ (resp.
$v_{4j+1}v_{4j}-u_{4j+1}u_{4j}+y_{4j+1}y_{4j}$) is the same as that of
$x_{4j+1}x_{4j}$ (resp. $y_{4j+1}y_{4j}$). It follows from Definition 4 that
$\psi(x)\psi(y)\in E(BSQ_{n})$.

Case 1.2. $v_{4j}$ is odd. Clearly, we have
$\psi(x_{4}^{j})=(v_{4j+1}v_{4j}-u_{4j+1}u_{4j}-x_{4j+1}x_{4j},v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}-x_{4j-1}x_{4j-2})$
and
$\psi(y_{4}^{j})=(v_{4j+1}v_{4j}-u_{4j+1}u_{4j}-y_{4j+1}y_{4j},v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}-y_{4j-1}y_{4j-2})$.
Observe that $xy\in E(BSQ_{n})$.

If $x_{4j}$ is even, then $y_{4j-1}y_{4j-2}\equiv
x_{4j-1}x_{4j-2}+1(\text{mod}\ 4)$. Thus, $-y_{4j-1}y_{4j-2}\equiv-
x_{4j-1}x_{4j-2}-1(\text{mod}\ 4)$. So
$v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}-y_{4j-1}y_{4j-2}\equiv
v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}-x_{4j-1}x_{4j-2}-1(\text{mod}\ 4)$. Now we
see that $v_{4j+1}v_{4j}-u_{4j+1}u_{4j}-x_{4j+1}x_{4j}$ is odd and
$v_{4j+1}v_{4j}-u_{4j+1}u_{4j}-y_{4j+1}y_{4j}$ is even. By Definition 4, we
have $\psi(x)\psi(y)\in E(BSQ_{n})$.

If $x_{4j}$ is odd, then $y_{4j-1}y_{4j-2}\equiv
x_{4j-1}x_{4j-2}-1(\text{mod}\ 4)$. Thus, $-y_{4j-1}y_{4j-2}\equiv-
x_{4j-1}x_{4j-2}+1(\text{mod}\ 4)$. So
$v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}-y_{4j-1}y_{4j-2}\equiv
v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}-x_{4j-1}x_{4j-2}+1(\text{mod}\ 4)$. Now we
see that $-v_{4j+1}v_{4j}+u_{4j+1}u_{4j}-x_{4j+1}x_{4j}$ is even and
$-v_{4j+1}v_{4j}+u_{4j+1}u_{4j}-y_{4j+1}y_{4j}$ is odd. By Definition 4, we
have $\psi(x)\psi(y)\in E(BSQ_{n})$.

Case 2. $u_{4j}$ is odd.

Case 2.1. $v_{4j}$ is even. In this case, we have
$\psi(x_{4}^{j})\\!=\\!(\\!-v_{4j+1}\\!v_{4j}\\!+u_{4j+1}\\!u_{4j}-x_{4j+1}\\!x_{4j},-v_{4j-1}\\!v_{4j-2}\\!+u_{4j-1}\\!u_{4j-2}-x_{4j-1}\\!x_{4j-2}),$
and
$\psi(y_{4}^{j})\\!=\\!(\\!-v_{4j+1}\\!v_{4j}\\!+u_{4j+1}\\!u_{4j}-y_{4j+1}\\!y_{4j},-v_{4j-1}\\!v_{4j-2}\\!+u_{4j-1}\\!u_{4j-2}-y_{4j-1}\\!y_{4j-2})$.
Obviously, $-v_{4j+1}v_{4j}+u_{4j+1}u_{4j}-x_{4j+1}x_{4j}$ and
$-v_{4j+1}v_{4j}+u_{4j+1}u_{4j}-y_{4j+1}y_{4j}$ have different parities.
Observe that $xy\in E(BSQ_{n})$.

If $x_{4j}$ is even, then $y_{4j-1}y_{4j-2}\equiv
x_{4j-1}x_{4j-2}+1(\text{mod}\ 4)$. Thus, $-y_{4j-1}y_{4j-2}\equiv-
x_{4j-1}x_{4j-2}-1(\text{mod}\ 4)$. Now we see that
$-v_{4j+1}v_{4j}+u_{4j+1}u_{4j}-x_{4j+1}x_{4j}$ is odd and
$-v_{4j+1}v_{4j}+u_{4j+1}u_{4j}-y_{4j+1}y_{4j}$ is even. By Definition 4, we
have $\psi(x)\psi(y)\in E(BSQ_{n})$.

If $x_{4j}$ is odd, then $y_{4j-1}y_{4j-2}\equiv
x_{4j-1}x_{4j-2}-1(\text{mod}\ 4)$. Thus, $-y_{4j-1}y_{4j-2}\equiv-
x_{4j-1}x_{4j-2}+1(\text{mod}\ 4)$. Now we see that
$-v_{4j+1}v_{4j}+u_{4j+1}u_{4j}-x_{4j+1}x_{4j}$ is even and
$-v_{4j+1}v_{4j}+u_{4j+1}u_{4j}-y_{4j+1}y_{4j}$ is odd. By Definition 4, we
have $\psi(x)\psi(y)\in E(BSQ_{n})$.

Case 2.2. $v_{4j}$ is odd. In this case, we have
$\psi(x_{4}^{j})=(v_{4j+1}v_{4j}-u_{4j+1}u_{4j}+x_{4j+1}x_{4j},v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}+x_{4j-1}x_{4j-2})$,
and
$\psi(y_{4}^{j})=(v_{4j+1}v_{4j}-u_{4j+1}u_{4j}+y_{4j+1}y_{4j},v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}+y_{4j-1}y_{4j-2})$.

If $x_{4j}$ is even, then $y_{4j-1}y_{4j-2}\equiv
x_{4j-1}x_{4j-2}+1(\text{mod}\ 4)$. We see that
$-v_{4j+1}v_{4j}+u_{4j+1}u_{4j}-x_{4j+1}x_{4j}$ is even and
$-v_{4j+1}v_{4j}+u_{4j+1}u_{4j}-y_{4j+1}y_{4j}$ is odd. By Definition 4, we
have $\psi(x)\psi(y)\in E(BSQ_{n})$.

If $x_{4j}$ is odd, then $y_{4j-1}y_{4j-2}\equiv
x_{4j-1}x_{4j-2}-1(\text{mod}\ 4)$. Now we see that
$-v_{4j+1}v_{4j}+u_{4j+1}u_{4j}-x_{4j+1}x_{4j}$ is odd and
$-v_{4j+1}v_{4j}+u_{4j+1}u_{4j}-y_{4j+1}y_{4j}$ is even. By Definition 4, we
have $\psi(x)\psi(y)\in E(BSQ_{n})$.

This completes the proof.∎

##  5\. Routing algorithms of SSQn and BSQn

In this section, we shall present the following shortest path algorithms of
SSQn and BSQn, respectively. We begin with the following assertion.

###### Theorem 7

. $d(SSQ_{n})=2$ for $n=2$ and $d(SSQ_{n})=\frac{n-2}{2}+2$ for $n>2$.

Proof. It is clear that the statement is true for $n=2$. In what follows, we
assume that $n>2$.

Let $u$ be a vertex of $SSQ_{n}$ with all bits zero. Since $SSQ_{n}$ is vertex
transitive, it suffices to determine $\max d(u,v)$ for any vertex $v\in
V(SSQ_{n})$. Thus, by Definition 2, for each $0\leq j\leq\frac{n-2}{4}$, there
are at most two steps from $u_{4}^{j}$ to $v_{4}^{j}$. Therefore, $\max
d(u,v)\leq\frac{n-2}{2}+2$.

On the other hand, let
$v=\underbrace{1101}\underbrace{1101}\cdots\underbrace{1101}11$ be a vertex of
$SSQ_{n}$. Thus, by Definition 2, for each $0\leq j\leq\frac{n-2}{4}$, there
are exactly two steps from $u_{4}^{j}$ to $v_{4}^{j}$, and each $u_{4}^{j}$
(resp. $v_{4}^{j}$) is independent to others. Thus, $d(u,v)=\frac{n-2}{2}+2$.

This completes the proof.∎

By the above statement, it is straightforward to obtain the following
algorithm.

Algorithm A (Routing algorithm of $SSQ_{n}$)
Input: $SSQ_{n}$ with $n>2$.
Output: a shortest path from an arbitrary vertex $v$ to $u$ in $SSQ_{n}$.
Initialization: $s\leftarrow h_{4}^{*}(v,u)$, $S=\\{j|v_{4}^{j}\neq u_{4}^{j}\
\text{and}\ j>0\\}$ if $v=u$
route into $u$
else
while $s>0$ do
arbitrarily choose $j\in S$
if $v_{4j+1}v_{4j}=u_{4j+1}u_{4j}$
then $v_{4}^{j}\leftarrow v_{4j+1}v_{4j}u_{4j-1}u_{4j-2}$ and route into $v$
else
if
$v_{4}^{j}=\overline{u}_{4j+1}\overline{u}_{4j}\overline{u}_{4j-1}\overline{u}_{4j-2}$
then
$v_{4}^{j}\leftarrow\overline{u}_{4j+1}\overline{u}_{4j}\overline{u}_{4j-1}\overline{u}_{4j-2}$
and route into $v$
else $w\leftarrow v$
$w_{4}^{j}\leftarrow\overline{u}_{4j+1}\overline{u}_{4j}\overline{u}_{4j-1}\overline{u}_{4j-2}$
and route into $w$
$x\leftarrow w$
$x_{4j-1}x_{4j-2}\leftarrow v_{4j-1}v_{4j-2}$ and route into $x$
$v\leftarrow x$
$s\leftarrow s-1$
$S\leftarrow S\setminus\\{j\\}$
end while
if $v_{1}v_{0}=u_{1}u_{0}$
route into $u$
else route into the neighbor $w$ of $v$ that changes $v_{1}v_{0}$ in a cyclic
manner with respect to 00, 01, 10, 11

The correctness of Algorithm A is shown as follows.

###### Theorem 8

. Algorithm A generates a shortest path from a vertex $u$ to $v$ in $SSQ_{n}$.

Proof. Based on Theorem 7, by recursively changing each $u_{4}^{j}$ to
$v_{4}^{j}$ for each $0\leq j\leq\frac{n-2}{4}$, we can obtain a shortest path
from $u$ to $v$.∎

To determine the diameter of the $BSQ_{n}$, we have the following result.

###### Theorem 9

. $d(BSQ_{n})=n$ whenever $n\geq 2$.

Proof. It is clear that the statement is true for $n=2$. In what follows, we
assume that $n>2$.

Let $u$ be a vertex of $BSQ_{n}$ with all bits zero. Since $BSQ_{n}$ is vertex
transitive, it suffices to determine $\max d(u,v)$ for any vertex $v\in
V(BSQ_{n})$. Thus, by Definition 4, for each $1\leq j\leq\frac{n-2}{4}$, there
are at most four steps from $u_{4}^{j}$ to $v_{4}^{j}$, and there are exactly
two steps from $u_{4}^{0}$ to $v_{4}^{0}$. Therefore, $\max d(u,v)\leq n$.

On the other hand, let
$v=\underbrace{1111}\underbrace{1111}\cdots\underbrace{1111}11$ be a vertex of
$BSQ_{n}$. Thus, by Definition 4, for each $1\leq j\leq\frac{n-2}{4}$, there
are exactly four steps from $u_{4}^{j}$ to $v_{4}^{j}$, and each $u_{4}^{j}$
(resp. $v_{4}^{j}$) is independent to others. In addition, there are exactly
two steps from $u_{4}^{0}$ to $v_{4}^{0}$. Thus, $d(u,v)=n$.

This completes the proof.∎

###### Theorem 10

. Let $u$ and $v$ be two distinct vertices of $BSQ_{n}$ ($n>2$) such that
$u_{4j+1}\neq v_{4j+1}$, $u_{4j}u_{4j-1}u_{4j-2}=v_{4j}v_{4j-1}v_{4j-2}$ for
some $j\in\\{1,\cdots,\frac{n-2}{4}\\}$ and $u_{4}^{i}=v_{4}^{i}$ for each
$i\in\\{1,\cdots,\frac{n-2}{4}\\}\setminus\\{j\\}$. Then $u$ and $v$ have the
same neighborhood.

Proof. It can be easily derived from Definition 4. ∎

Remark 2. For convenience, if $u$ and $v$ are two distinct vertices satisfy
the condition (thus have the same neighborhood) in the above theorem, then we
say $u$ is equivalent to $v$, denote by $u\equiv v$. Without cause of
ambiguity, we also denote $u_{4}^{j}\equiv v_{4}^{j}$. Moreover, for an
arbitrary vertex $u$, there are exactly $\frac{n-2}{4}$ distinct vertices of
$BSQ_{n}$ ($n>2$) that are equivalent to $u$ respectively.

We present the routing algorithm of $BSQ_{n}$ as follows.

Algorithm B (Routing algorithm of $BSQ_{n}$)
Input: $BSQ_{n}$ with $n>2$.
Output: a shortest path from an arbitrary vertex $v$ to $u$ in $BSQ_{n}$.
Initialization: $s\leftarrow h_{4}^{*}(v,u)$, $S=\\{j|v_{4}^{j}\neq u_{4}^{j}\
\text{and}\ j>0\\}$ if $v=u$
route into $u$
else
while $s>0$ do
arbitrarily choose $j\in S$
if $v_{4j-1}v_{4j-2}=u_{4j-1}u_{4j-2}$
if $v_{4}^{j}\equiv u_{4}^{j}$
then $s\leftarrow s-1$
$S\leftarrow S\setminus\\{j\\}$
else
then route into the neighbor $w$ of $v$ that changes $v_{4j+1}v_{4j}$ in a
cyclic manner with respect to 00, 01, 10, 11
$s\leftarrow s-1$
$S\leftarrow S\setminus\\{j\\}$
else
if ($v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}=1\wedge v_{4j}$ is
odd)$\vee(v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}=3\wedge v_{4j})$ is even
then $v_{4}^{j}\leftarrow u_{4}^{j}$ and route into $v$
$s\leftarrow s-1$
$S\leftarrow S\setminus\\{j\\}$
else if ($v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}=1\wedge v_{4j}$ is
even)$\vee(v_{4j-1}v_{4j-2}-u_{4j-1}u_{4j-2}=3\wedge v_{4j})$ is odd
then $v_{4j+1}v_{4j}\leftarrow v_{4j+1}v_{4j}+1$ and route into $v$
else
$v_{4j+1}v_{4j}\leftarrow v_{4j+1}v_{4j}+1$ and $v_{4j-1}v_{4j-2}\leftarrow
v_{4j-1}v_{4j-2}+(-1)^{v_{4j}}$
route into $v$
end while
if $v_{1}v_{0}=u_{1}u_{0}$
route into $u$
else route into the neighbor $w$ of $v$ that changes $v_{1}v_{0}$ in a cyclic
manner with respect to 00, 01, 10, 11

###### Theorem 11

. Algorithm B generates a shortest path from a vertex $u$ to $v$ in $BSQ_{n}$.

Proof. Based on Theorem 9, by recursively changing each $u_{4}^{j}$ to
$v_{4}^{j}$ for each $0\leq j\leq\frac{n-2}{4}$, we can obtain a shortest path
from $u$ to $v$.∎

##  6\. Hamiltonian cycle embedding of $SSQ_{n}$ and $BSQ_{n}$

The Hamiltonian ring embedding of interconnection network, which provide
advantages for algorithms that make use of a ring structure, is an important
issue for multiprocessor systems [3]. In this section, we study Hamiltonian
cycle embedding of $SSQ_{n}$ and $BSQ_{n}$ respectively, implying $SSQ_{n}$
and $BSQ_{n}$ are both Hamiltonian.

###### Theorem 12

. There exists a Hamiltonian cycle in $SSQ_{n}$ for $n>2$.

Proof. We construct a Hamiltonian cycle $H_{1}$ of $SSQ_{n}$ for $n>2$. Start
$H_{1}$ with the vertex
$u=\underbrace{0000}\underbrace{0000}\cdots\underbrace{0000}00$ by changing
$u_{4}^{1}$. Since each vertex is contained in exactly one $K_{4}$ of
$SSQ_{n}$, it is easy to find a Hamiltonian path $P_{1}$ of this $K_{4}$
(vertices with the first 4-bit 00**) from $u$ to
$u_{1}=\underbrace{0011}\underbrace{0000}\cdots\underbrace{0000}00$, where “*”
means the bit we do not care. Note that
$u_{1}^{\prime}=\underbrace{1100}\underbrace{0000}\cdots\underbrace{0000}00$
is a neighbor of $u_{1}$, and $u_{1}$ is contained in exactly one $K_{4}$ with
the first 4-bit 11**. Similarly, there exists a Hamiltonian path $P_{2}$ of
this $K_{4}$ (vertices with the first 4-bit 11**) from $u_{1}^{\prime}$ to
$u_{1}^{\prime\prime}=\underbrace{1111}\underbrace{0000}\cdots\underbrace{0000}00$.
Concatenating $P_{1}$ and $P_{2}$ yields a path $P$ with eight vertices.

We then iteratively change $u_{4}^{j}$ ($1\leq j\leq\frac{n-2}{4}-1$) one step
as the first 4-bit of the vertices varying on $P$, to reach a new neighbor. In
particular, if $j=0$, then we change $u_{4}^{0}=u_{1}u_{0}$ one step in a
cyclic manner with respect to 00, 01, 10, 11. Since we have arrived at a
vertex with distinct $u_{4}^{j}$, we change its first 4-bit as in the manner
above. Consequently, we can obtain a Hamiltonian cycle of $SSQ_{n}$ for $n\geq
2$.

This completes the proof.∎

To illustrate the approach used in the proof of Theorem 12, we give the
following example.

Example 1. To obtain a Hamiltonian cycle $H_{1}$ of $SSQ_{6}$, we starts
$H_{1}$ at $u=000000$ as follows:

$\begin{array}[]{lll}H_{1}:&000000{\rightarrow}000100{\rightarrow}001000{\rightarrow}001100{\rightarrow}110000{\rightarrow}110100{\rightarrow}111000{\rightarrow}111100{\rightarrow}\\\
&111101{\rightarrow}111001{\rightarrow}110101{\rightarrow}110001{\rightarrow}001101{\rightarrow}001001{\rightarrow}000101{\rightarrow}000001{\rightarrow}\\\
&000010{\rightarrow}000110{\rightarrow}001010{\rightarrow}001110{\rightarrow}110010{\rightarrow}110110{\rightarrow}111010{\rightarrow}111110{\rightarrow}\\\
&111111{\rightarrow}111011{\rightarrow}110111{\rightarrow}110011{\rightarrow}001111{\rightarrow}001011{\rightarrow}000111{\rightarrow}000011{\rightarrow}\\\
&000000\end{array}$

###### Lemma 13

. There exists a Hamiltonian cycle of $BSQ_{6}$.

Proof. We construct a Hamiltonian cycle $H_{2}$ of $BSQ_{6}$ by greedily
changing the first two bits of vertices in a cyclic manner with respect to 00,
01, 10, 11 as follows:

$\begin{array}[]{lll}H_{2}:&000000{\rightarrow}010000{\rightarrow}100000{\rightarrow}110000{\rightarrow}001100{\rightarrow}011100{\rightarrow}101100{\rightarrow}111100{\rightarrow}\\\
&001000{\rightarrow}011000{\rightarrow}101000{\rightarrow}111000{\rightarrow}000100{\rightarrow}010100{\rightarrow}100100{\rightarrow}110100{\rightarrow}\\\
&110101{\rightarrow}000101{\rightarrow}010101{\rightarrow}100101{\rightarrow}111001{\rightarrow}001001{\rightarrow}011001{\rightarrow}101001{\rightarrow}\\\
&111101{\rightarrow}001101{\rightarrow}011101{\rightarrow}101101{\rightarrow}110001{\rightarrow}000001{\rightarrow}010001{\rightarrow}100001{\rightarrow}\\\
&100010{\rightarrow}110010{\rightarrow}000010{\rightarrow}010010{\rightarrow}101110{\rightarrow}111110{\rightarrow}001110{\rightarrow}011110{\rightarrow}\\\
&101010{\rightarrow}111010{\rightarrow}001010{\rightarrow}011010{\rightarrow}100110{\rightarrow}110110{\rightarrow}000110{\rightarrow}010110{\rightarrow}\\\
&010111{\rightarrow}100111{\rightarrow}110111{\rightarrow}000111{\rightarrow}011011{\rightarrow}101011{\rightarrow}111011{\rightarrow}001011{\rightarrow}\\\
&011111{\rightarrow}101111{\rightarrow}111111{\rightarrow}001111{\rightarrow}010011{\rightarrow}100011{\rightarrow}110011{\rightarrow}000011{\rightarrow}\\\
&000000\end{array}$

∎

By the proof of Lemma 13, it is known that each path $uvwx$ is contained in
$H_{2}$, where $u_{5}u_{4}=00,v_{5}v_{4}=01,w_{5}w_{4}=10,x_{5}x_{4}=11$, and
$u_{3}u_{2}u_{1}u_{0}=v_{3}v_{2}v_{1}v_{0}=w_{3}w_{2}w_{1}w_{0}=x_{3}x_{2}x_{1}x_{0}$.
By Remark 2, $u$ and $w$ have the same neighborhood, meanwhile, $v$ and $x$
have the same neighborhood. Since $BSQ_{n}$ is vertex-transitive, each edge of
the cycle $uvwxu$ can be in a Hamiltonian cycle of $BSQ_{6}$ by modifying
$H_{2}$ through equivalent vertices.

###### Theorem 14

. There exists a Hamiltonian cycle in $BSQ_{n}$ for $n>2$.

Proof. For convenience, let $k=\frac{n-2}{4}$. We prove this theorem by
induction on $k$. Obviously, by Lemma 13 the statement is true for $k=1$
($n=6$). Assume that the statement is true for $k-1$ ($k\geq 2$). Next we
consider $BSQ_{n}$ ($n=4k+2$). For some $i$ ($1\leq i\leq\frac{n-2}{4}$), all
the vertices of the same $u_{4}^{i}$ form a subcube $BSQ_{n-4}$. Suppose
w.l.o.g. that $i=\frac{n-2}{4}$ and $j=\frac{n-2}{4}-1$. By Definition 4,
there exist sixteen subcubes $BSQ_{n-4}$ with different $u_{4}^{i}$s
respectively.

We construct a Hamiltonian cycle of $BSQ_{n}$ from $u=000000000000\cdots 00$.
Since we only consider the first two 4-bits of the vertices in the remainder
of the proof, for simplicity, we write $u=00000000$. Clearly, $u$ has a
neighbor $v=00000100$ in another $BSQ_{n-4}$. For convenience, let
$w=01000100$. By induction hypothesis, this $BSQ_{n-4}$ has a Hamiltonian
cycle $H_{1}$ containing the edge $vw$. Similarly, $w$ has a neighbor
$u_{1}=01001000$. By repeatedly using the above method, a Hamiltonian cycle
$H$ of $BSQ_{n}$ follows (see Fig. 4), completing the proof.∎

Fig. 4: Construction of Hamiltonian cycle of $BSQ_{n}$.

##  7\. Conclusions

The shuffle cube $SQ_{n}$ was proposed by Li et al. [20] to enhance some
properties of the hypercube. Symmetry is a desirable property in
interconnection networks. In this paper, we study the symmetric properties of
the shuffle cube $SQ_{n}$, showing that $SQ_{n}$ is not vertex-transitive and
edge-transitive for all $n>2$. To address this shortcoming of the shuffle-
cube, we propose two variants of the shuffle cube, simplified shuffle cube
$SSQ_{n}$ and balanced shuffle cube $BSQ_{n}$ and show that they are both
vertex-transitive. We also design routing schemes for $SSQ_{n}$ and $BSQ_{n}$,
respectively. In addition, we show that both $SSQ_{n}$ and $BSQ_{n}$ admit a
Hamiltonian cycle. For a future research, it is worthwhile to study other
combinatorial properties of the two variants we have introduced, such as
fault-tolerant Hamiltonian cycle embedding, edge-disjoint Hamiltonian cycle
embedding, super (edge) connectivity, etc.

## References

  * [1] S. Abraham, K. Padmanabhan, The twisted cube topology for multiprocessors: a study in network asymmetry, J. Parallel Distrib. Comput. 13 (1991) 104–110.
  * [2] S.B. Akers, B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput. 38 (4) (1989) 555-566.
  * [3] B. Albader, B. Bose, Edge disjoint Hamiltonian cycles in Gaussian networks, IEEE Trans. Comput. 65 (2016) 315–321.
  * [4] S. Antantapantula, C. Melekian, and E. Cheng, Matching preclusion for the shuffle-cubes, Parallel Process. Lett. 28 (3) (2018), 1850012.
  * [5] N. Ascheuer, Hamiltonian Path Problems in the On-line Optimization of Flexible Manufacturing Systems, Ph.D. Thesis, University of Technology, Berlin, Germany, 1995.
  * [6] W.C. Athas, C.L. Seitz, Multicomputers: message-passing concurrent computers, Computer 21 (1988) 9–24.
  * [7] L.N. Bhuyan, D.P. Agrawal, Generalized hypercube and hyperbus structures for a computer network, IEEE Trans. Comput. 32 (4) (1984) 323–333.
  * [8] J.A. Bondy, U.S.R. Murty, Graph theory, Springer, New York, 2007.
  * [9] J.P. Brunet, S.L. Johnsson, All-to-All broadcast and applications on the connection machine, Inter. J. High Perf. Comput. Appl. 6 (1992) 241–256
  * [10] P. Cull, S.M. Larson, The Möbius cubes: Improved cubelike networks for parallel computation, in: Proc. 6th Int. Parallel Process. Symp., Beverly Hills, CA, IEEE Comput. Soc., March 1992, pp. 610 C615.
  * [11] T. Ding, P. Li, M. Xu, The component (edge) connectivity of shuffle-cubes, Theoret. Comput. Sci. 835 (2020) 108–119
  * [12] T.H. Dunican, Performance of the Intel iPSC/860 and ncube 6400 hypercubes, Parallel Computing 17 (1991) 1285–1302.
  * [13] A. El-Amawy, S. Latifi, Properties and performance of folded hypercubes, IEEE Trans. Parallel Distrib. Syst. 2 (1991) 31–42.
  * [14] J.P. Hayes, T.N. Mudge, Hypercube Supercomputers, Proc. IEEE 77 (12) (1989) 1829–1841.
  * [15] M.C. Heydemann, Cayley graphs and interconnection networks, graph symmetry, G. Hahn and G. Sabidussi, eds., pp. 167-224, Kluwer Academic Publishing, 1997.
  * [16] W.-J Hsu, Fibonacci cubes–a new interconnection topology, IEEE Trans. Parallel Distrib. Syst. 4 (1993) 3–12
  * [17] W.T. Huang, M.Y. Lin, J.M. Tan, L.H. Hsu, Fault-tolerant ring embedding in faulty crossed cubes, Proc. SCI 2000, pp. 97–102, 2000.
  * [18] B. Khosravi, B. Khosravi, B. Khosravi, Routing algorithms for the shuffle-exchange permutation network, J. Supercomput. 77 (2021) 11556–11574.
  * [19] S. Lakshmivarahan, J.S. Jwo, S.K. Dhall, Symmetry in interconnection networks based on Cayley graphs of permutation groups: a survey, Parallel Comput. 19 (1993) 361–407.
  * [20] T.-K. Li, J.J.M. Tan, L.-H. Hsu, T.-Y. Sung, The shuffle-cubes and their generalization, Inform. Process. Lett. 77 (2001) 35–41.
  * [21] T.K. Li, J.J.M. Tan, L.H. Hsu, Fault hamiltonicity of the shuffle-cubes, Researchgate Net (2013) 110–119.
  * [22] R. Libeskind-Hadas, R.G. Melhem, Multicast routing and wavelength assignment in multihop optical networks, IEEE/ACM Trans. Netw. 10 (5) (2002) 621–629.
  * [23] L. Lin, L. Xu, S. Zhou, Conditional diagnosability and strong diagnosability of shuffle-cubes under the comparison model, Int. J. Comput. Math. 92 (2) (2015) 230–249.
  * [24] Y.-L. Liu, Routing and wavelength assignment for exchanged hypercubes in linear array optical networks, Inf. Process. Lett. 115, Issue (2015) 203–208
  * [25] P.K.K. Loh, W.J. Hsu, Y. Pan, The exchanged hypercube, IEEE Trans. Parallel Distrib. Syst. 16 (9) (2005) 866–874.
  * [26] M.E. Munarini, C.P. Cippo, N. Zagaglia Salvi, On the Lucas cubes, Fibonacci Quarterly 39 (2001) 12–21.
  * [27] NCUBE Corporation, NCUBE Handbook, Beaverton, Ore., 1986.
  * [28] J.-H. Park, H.-C. Kim, H.-S. Lim, Many-to-many disjoint path covers in presence of faulty elements, IEEE Trans. Comput. 58 (4) (2009) 528–540.
  * [29] X.-W. Qin, R.-X. Hao, Reliability analysis based on the dual-CIST in shuffle-cubes, Appl. Math. Comput. 397 (2021), 125900.
  * [30] C.L. Seitz, The Cosmic Cube, Comm. ACM 28 (1985) 22–33.
  * [31] N.K. Singhvi, K. Ghose, The Mcube: A symmetrical cube based network with twisted links, in: Proc. of the 9th Int. Parallel Processing Symp., IEEE Comput. Soc., Los Alamitos, CA, April 1995, pp. 11–16.
  * [32] J. Wu, K. Huang, The balanced hypercube: a cube-based system for fault-tolerant applications, IEEE Trans. Comput. 46 (4) (1997) 484–490.
  * [33] J. Xu, M. Xu, Q. Zhu, The super connectivity of shuffle-cubes, Inf. Process. Lett. 96 (4) (2005) 123–127.
  * [34] M. Xu, X. Hu, S. Shang, The conditional diagnosability of shuffle-cubes, J. Sys. Sci. Complex. 23 (1) (2010) 81–90.
  * [35] C. Yu, X. Yang, L. Yang, J. Zhang, Routing and wavelength assignment for 3-ary $n$-cube in array-based optical network, Inf. Process. Lett. 112 (2012) 252–256.