#  DILATION TWO EMBEDDING ONE-BY-ONE PARTICULAR SUB-QUADTREE INTO
$\mathbf{M}$-DIMENTIONAL CROSSED CUBES

Aymen Takie Eddine Selmi<EMAIL_ADDRESS>Mohamed Faouzi Zerarka
<EMAIL_ADDRESS>Abdelhakim Cheriet<EMAIL_ADDRESS>Departement of computer science and LESIA Laboratory, Mohamed Khider
University of Biskra, Algeria  Departement of computer science, Mohamed Khider
University of Biskra, Algeria.  Department of computer science and information
technology, Kasdi Merbah University of Ouargla, Algeria.

###### Abstract

In the parallel processing field, graph embedding is motivated by simulation
interconnection networks to another. The quadtree is an important technique
used to present spatial data and is used in many application domains,
especially computer vision and image processing. Researchers are interested in
the construction and manipulation of quadtrees on parallel machines. The
crossed cubes consider an alternative to the ordinary hypercube. It offers
many attractive properties. Significantly, it reduces diameter by a factor of
2 that of the ordinary cubes. Moreover, the crossed cubes have a great
capacity to simulate other architectures. This paper is interested in the one-
by-one dilation two embedding of a particular sub-quadtree graph into
m-dimensional crossed cubes.

###### keywords:

Interconnection networks, crossed cubes, quadtree, embedding, dilation.

††journal: Journal Name

##  1 Introduction

For a machine based on parallel architecture, the choice of a good topology is
linked to a set of attractive and popular properties such as degree, diameter,
connectivity, regularity, embeddability, and fault tolerance.

The quadtree is an important technique used in many application domains such
as geographic information systems, image processing, computer graphics,
robotics [1, 2, 3, 4, 5]. The quadtree is a simple topology; it is a connected
graph with a cycle in which each internal vertex has four children. Suppose
all left child breaks down; quadtree will be a particular sub-quadtree. This
technique has a set of limits. It has a bisection width equal to 1 [6].
Moreover, its connectivity equal to 1 [6]. Therefore, many researchers studied
the embedding of quadtrees into another interconnection network [7, 8, 9, 10].

Parallel machines based on hypercube topology offer an interconnection
topology with attractive properties: symmetry, logarithmic diameter, fixed
degree, high connectivity, Hamiltonian, fault tolerance, extensibility, and
embeddability of other topologies [11, 12, 13, 14, 10, 15, 16]. Several
researchers propose several versions of the hypercube to improve its capacity.
In the papers by Ahmed El-Amawy[17] and Preparata & Vuillemin [18], an
attractive version of the hypercube called the crossed cubes is proposed by
Efe [19]. This version pays attention because of the similarity in properties
with the ordinary hypercube. Also, it offers many popular attractive
properties over the ordinary hypercube [10, 20, 21, 22, 23, 24, 25].
Especially, it reduces diameter by a factor of 2 [19]. Moreover, the crossed
cubes have a great capacity to simulate other architectures [10, 15, 26, 27,
28, 29]. The problem of simulation of one interconnection network to another
is essential in the field of parallel computing. The embedding capabilities
are important in evaluating an interconnection network.

Let _G_ and _H_ be two graphs such that an embedding of _G_ into _H_ is a pair
(_f_ , _R_) where _f_ is an injective mapping vertex _V_(_G_) into vertex
_V_(_H_). _R_ is an injective mapping associating with each edge [_u_ , _v_]
from $G$ at a path _R_(_u_ , _v_) which connects _f_(_u_) and _f_(_v_) [30,
31, 32].

This paper aims to construct the dilation two embedding one-by-one particular
sub-quadtree into $m$-dimensional crossed cubes. This paper is organized as
follows; first, we introduce a few preliminary definitions of the particular
sub-quadtree graph and the crossed cubes graph. Section 3 presents the
construction of dilation two one-by-one particular sub-quadtree into
$m$-dimensional crossed cubes; then, we offer the validation of our new
function. Finally, section 4 concludes the paper and discusses some possible
future work.

##  2 PRELIMINARIES

###  2.1 Definition 01

The quadtree is an undirected graph _QT_ n of $(4^{n}-1)/3$ vertices. Every
vertex of depth less than $n$ has four children, and every vertex of depth
equal to $n$ is a leaf. We assume each left child breaks down, quadtree
reduced to a particular sub-quadtree graph denoted _PQT n_. Therefore,
quadtree will become an undirected graph _PQT n_ of $(3{{}^{n}}-1)/2$
vertices. Let $p$ be a positive integer, each vertex in _PQT n_ is a string of
length $p$ denoted _AV_ $=$ _Aa p-1suffi_; where _A_ p-1 $=$ _a
1a2$\dots$aj$\dots$ap-1_, a${}_{j}=\overline{1,3}$ and _suff i_ $=$ $i$ /
$i=\overline{1,3}$. The root can represent by address $a_{1}$ $=$ $0$. We
represent an edge between a vertex parent and one of its children as follows,
_A p-1_-_A p-1suffi_.

###  2.2 Definition 02 [19]

Both the $m$-dimensional hypercube denoted by _Q m_ and the crossed cubes _CQ
m_ are undirected graphs consisting of the same set of vertices. A binary
string of length $m$ labels each vertex in _Q m_(_CQ m_). In _Q m_, two
vertices are adjacent if and only if the binary representation of their labels
differs in exactly one-bit position. While in the crossed cubes, two binary
strings _x_ $=$ _x 1x0_, _y_ $=$ _y 1y0 _ of length two are pair-related if
and only if $(\emph{x},\emph{y})\in\\{(00,00),(10,10),(01,11),(11,01)\\}$. The
$m$-dimensional crossed cubes _CQ m_ is defined recursively:

  * 1.

_CQ 1_ is the complete graph on two vertices with labels 0 and 1.

  * 2.

If $m$ $>$ 1: _CQ_ m consists of two sub-cubes, 0 _CQ_ m-1 and 1 _CQ m-1_. Two
vertices $u$, $v$ such that $u$ $=$ $0u_{m-2}...u_{0}\in$ 0 _CQ_ m-1, and $v$
$=$ $1v_{m-2}...v_{0}\in$ 1 _CQ_ m-1 are adjacent, if and only if:
_u_ m-2 $=$ _v_ m-2 if $m$ is even
_u_ 2i+1 _u_ 2i, _v_ 2i+1 _v_ 2i are pair-related.

###  2.3 Definition 03 [32, 33]

Let _G_ and _H_ be two simple undirected graphs. An embedding of the graph _G_
into graph _H_ is an injective mapping _f_ from the vertices of _G_ to the
vertices of _H_. Four cost functions, dilation, congestion, expansion, and
load factor, often measure the quality of an embedding. In this paper, we
interest in dilation. The dilation of the embedding is the maximum distance
between _f_(_y_) and _f_(_z_) taken over all edges (_y_ , _z_) of _G_.

###  2.4 Notations

A particular sub-quadtree _PQT_ n is produced by three copies of _PQT_ n-1
prefixed respectively by $01$_PQT_ n-1, $02$_PQT_ n-1, $03$_PQT_ n-1, and a
root prefixed by $0$_PQT_ n.

A crossed cubes _CQ_ m $=$ (_O_ , _E_), with _E_ set of vertices and _O_ set
of edges.

Let $B\in E$ such that: $B$ $=$ $C$_pref_ j$X_{3}X_{2}X_{1}X_{0}$;
${\color[rgb]{0,0.88,0}C}={{\color[rgb]{0,0.88,0}b_{r-1}},{\color[rgb]{0,0.88,0}\bar{b}_{r-1}},\phi}$;
$adrr=X,Y,Z$, $adrr$ $=X_{1}X_{0}$ of length two and ($X,Y$) or ($Y,Z$) are
pair-related; _Pref_ j $=$ $b_{k}\dots b_{m-4}$ / $j$ $=$ $\overline{0,3}$
respectively if $b_{r}b_{r+1},b_{r}\bar{b}_{r+1}$, $\bar{b}_{r}b_{r+1}$,
$\bar{b}_{r}\bar{b}_{r+1}$. The number of super nodes _CQ_ 4 is equal to 2m-4.

_CQ_ m is produced as follows:
Where $C=\phi$: _CQ_ m is produced by four copies of _CQ_ m-2 prefixed
respectively by $00$_CQ_ l-2, $01$_CQ_ l-2, $10$_CQ_ l-2, $11$_CQ_ l-2.
Where $C\neq\phi$: _CQ_ m is produced by two copies of _CQ_ m-1 prefixed
respectively by $0$_CQ_ m-1, $1$_CQ_ m-1 in other word: $00$_CQ_ m-2, $01$_CQ_
m-2, $10$_CQ_ m-2, $11$_CQ_ m-2.

##  3 DILATION TWO EMBEDDING ONE-BY-ONE PARTICULAR SUB-QUADTREE INTO
M-DIMENSIONAL CROSSED CUBES

This section describes our new function, which allows the embedding one-by-one
particular sub-quadtree _PQT n_ into $m$-dimensional crossed cubes _CQ_ m. We
can resume this function as follows:

  * 1.

Determine the dimension of the crossed cubes _CQ_ m.

  * 2.

One-by-one vertex embedding of _PQT n_ into _CQ_ m.

  * 3.

Dilation two embedding one-by-one all edges of _PQT n_ onto paths in _CQ_ m.

###  3.1 Dimension of _CQ_ m

The dimension of the crossed cubes $m$ related by $n$ the height of a
particular sub-quadtree in which:

  * 1.

Where $n\leq 8$: $m=log_{2}((3^{n}-1)/2))/log_{2}(2)$

  * 2.

Where $n>8$: $m=(n-8)*2+12$

###  3.2 One-by-one vertex embedding

The one-by-one vertex embedding of _PQT n_ into _CQ_ m is done in the
following way:
For $n=3$: The basic function _f_ of this one by one vertex embedding is
produced as follows:

  * 1.

_Prem(0) := pref 0$00$_

  * 2.

_f(A p-1suff1) := Pref1$X$_

  * 3.

_f(A p-1suff2) := Pref2$Y$_

  * 4.

_f(A p-1suff3) := Pref3$Z$_

For $n>3$: the one-by-one vertex embedding is done in two situations. The
first one is when $C=\phi$, we use the basic function _f_ (figure 1).

Figure 1: Vertex embedding Situation 1

The second is when $C\neq\phi$; a function _f_ 1 of this one-by-one vertex
embedding. Thus, there three cases in this situation; the following rules of
case 1 shown in figure 2 produce _f_ 1:

  * 1.

_f 1(Ap-1suff1) := $0$Pref1$00X$_

  * 2.

_f 1(Ap-1suff2) := $1$Pref1$00Y$_

  * 3.

_f 1(Ap-1suff3) := $1$Pref0$00Z$_

OR

  * 1.

_f 1(Ap-1suff1) := $\bar{0}$Pref1$00X$_

  * 2.

_f 1(Ap-1suff2) := $\bar{1}$Pref1$00Y$_

  * 3.

_f 1(Ap-1suff3) := $1$Pref0$00Z$_

Figure 2: Vertex embedding situation 2, case 1.

The following rules of case 2 shown in figure 3 produce _f_ 1:

  * 1.

_f 1(Ap-1suff1) := $\bar{0}$Pref0$00X$_

  * 2.

_f 1(Ap-1suff2) := $\bar{1}$Pref0$00Y$_

  * 3.

_f 1(Ap-1suff3) := $1$Pref0$00Z$_

Figure 3: Vertex embedding situation 2, case 2.

The following rules of case 3 shown in figure 4 produce _f_ 1 ($t$ $=$ 2, 3):

  * 1.

_f 1(Ap-1suff1) := $\bar{0}$Pref1$00X$_

  * 2.

_f 1(Ap-1suff2) := $\bar{1}$Pref1$00Y$_

  * 3.

_f 1(Ap-1suff3) := $\bar{1}$Pref1$00Z$_

OR

  * 1.

_f 1(Ap-1suff1) := $\bar{0}$Preft$00X$_

  * 2.

_f 1(Ap-1suff2) := $1$Preft$00Y$_

  * 3.

_f 1(Ap-1suff3) := $\bar{1}$Preft$00Z$_

Figure 4: Vertex embedding situation 2, case 3.

Lemma 1. For $n<5$, a particular sub-quadtree _PQT n_ is one-by-one vertex
embedding into $m$-dimensional crossed cubes _CQ_ m.
Proof. We prove lemma 1 by induction on $n$.
Base. For $n=2$: as shown in figure 5.
For $n=3,4$: level’s 1, 2 nodes of _PQT_ 3, _PQT_ 4 are respectively embedded
into _CQ_ 4, _CQ_ 6 using the rules specified in table 1, table 2, shown in
figure 6, figure 7.

Figure 5: Nodes embedding graph of _PQT_ 2 into _CQ_ 2.

_Root_ | _Prem(root)_ |  $0$_suff_ 1 |  $01$_CQ_ 2
---|---|---|---
${\color[rgb]{0,0,1}0}$ | ${\color[rgb]{1,0,0}00}00$ | $0{\color[rgb]{0,0,1}1}$ | ${\color[rgb]{1,0,0}01}00$
$0$_suff_ 2 |  $10$_CQ_ 2 |  $0$_suff_ 3 |  $11$_CQ_ 2
$0{\color[rgb]{0,0,1}2}$ | ${\color[rgb]{1,0,0}10}00$ | $0{\color[rgb]{0,0,1}3}$ | ${\color[rgb]{1,0,0}11}00$

Table 1: Level’s 1, 2 nodes embedding of _PQT_ 3 into _CQ_ 4 Figure 6: Nodes
embedding graph of _PQT_ 3 into _CQ_ 4.

_Root_ | _Prem(root)_ |  $0$_suff_ 1 |  $01$_CQ_ 4
---|---|---|---
${\color[rgb]{0,0,1}0}$ | ${\color[rgb]{1,0,0}00}0000$ | $0{\color[rgb]{0,0,1}1}$ | ${\color[rgb]{1,0,0}01}0000$
$0$_suff_ 2 |  $10$_CQ_ 4 |  $0$_suff_ 3 |  $11$_CQ_ 4
$0{\color[rgb]{0,0,1}2}$ | ${\color[rgb]{1,0,0}10}0000$ | $0{\color[rgb]{0,0,1}3}$ | ${\color[rgb]{1,0,0}11}0000$

Table 2: Level’s 1, 2 nodes embedding of _PQT_ 4 into _CQ_ 6. Figure 7: Nodes
embedding graph of _PQT_ 4 into _CQ_ 6.

Induction hypothesis

Suppose that for $k\leq n-1$, _PQT_ k is one-by-one vertex embedding into _CQ_
l with $l<m$ is true.
Let us now prove that it is true for $k=n$.

The root $0$ is embedded into $00$_CQ_ l-2 by using _Prem(root)_. Nodes _A_
k-1 _suff_ 1, _A_ k-1 _suff_ 2, _A_ k-1 _suff_ 3 are respectively embedded
into $01$_CQ_ l-2, $10$_CQ_ l-2, $11$_CQ_ l-2 using the basic function _f_
(induction hypothesis, shown in figure 1).

Lemma 2. For $n=5$, a particular sub-quadtree _PQT n_ is one-by-one vertex
embedding into $m$-dimensional crossed cubes _CQ_ m.
Proof. We prove lemma 2 by induction on $n$.
Base. For $n=5$: level’s 1, 2 nodes of _PQT_ 5 are embedded using the rules
specified in table 3 (figure 8).

_Root_ | _Prem(root)_ |  $0$_suff_ 1 |  $0$_pref 1CQ_4
---|---|---|---
${\color[rgb]{0,0,1}0}$ | ${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}00}0000$ | $0{\color[rgb]{0,0,1}1}$ | ${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}01}0000$
$0$_suff_ 2 |  $1$_pref 1CQ_4 |  $0$_suff_ 3 |  $1$_pref 0CQ_4
$0{\color[rgb]{0,0,1}2}$ | ${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}01}0000$ | $0{\color[rgb]{0,0,1}3}$ | ${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}00}0000$

Table 3: Level’s 1, 2 nodes embedding of _PQT_ 5 into _CQ_ 7. Figure 8: Nodes
embedding graph of _PQT_ 5 into _CQ_ 7.

Induction hypothesis

Suppose that for $k\leq n-1$, _PQT_ k is one-by-one vertex embedding into _CQ_
l with $l<m$ is true.
Let us now prove that it is true for $k$=$n$.

The root $0$ is embedded into $00$_CQ_ l-2 by using the basic function
_Prem(root)_. Nodes of $01$_PQT_ k-1 are embedded into $0$_CQ_ l-1 such that:
$0$_suff_ 1 is embedded into $0$_pref_ ${}_{1}0000$ of $00$_CQ_ l-2 using _f_
1 of situation 2, case 1 (figure 2, induction hypothesis). Other nodes of
$011$_PQT_ k-2, $012$_PQT_ k-2, $013$_PQT_ k-2 are respectively embedded into
the root embedded component, $01$_CQ_ l-2 of $0$_CQ_ l-1, and $01$_CQ_ l-2 of
$0$_CQ_ l-1 using _f_ (figure 1, induction hypothesis).

Nodes of $02$_PQT_ k-1 are embedded into $1$_CQ_ l-1 such that: $0$_suff_ 2 is
embedded into $1$_pref_ ${}_{1}0000$ of $10$_CQ_ l-2 by definition 02 using
_f_ 1 of situation 2, case 1 (figure 2). Other nodes of $021$_PQT_ k-2,
$022$_PQT_ k-2, $023$_PQT_ k-2 are respectively embedded into the same parent
component ($10$_CQ_ l-2), $11$_CQ_ l-2 of $1$_CQ_ l-1, and $11$_CQ_ l-2 of
$1$_CQ_ l-1 using _f_ (figure 1, induction hypothesis).

Nodes of $03$_PQT_ k-1 are embedded into _CQ_ l such that: $0$_suff_ 3 is
embedded into $1$_pref_ ${}_{0}0000$ of $10$_CQ_ l-2 by definition 02 using
_f_ 1 of situation 2, case 1 (figure 2); and $0$_$3$ suff_1 is embedded into
this same component $10$_CQ_ l-2 using _f_ 1 of situation 2, case 2 (figure 3,
induction hypothesis). Node $0$_$3$ suff_2 is embedded into $00$_CQ_ l-2 by
definition 02 using _f_ 1 of situation 2, case 2 (figure 3). Nodes of
$031$_PQT_ k-2, $032$_PQT_ k-2 are embedded into the same parent component,
respectively $10$_CQ_ l-2, $00$_CQ_ l-2 using _f_ (figure 1, induction
hypothesis).

Nodes of $033$_PQT_ k-2 are embedded into _CQ_ l such that: $0$_$3$ suff_3 is
embedded into the same parent component ($10$_CQ_ l-2) using _f_ 1 of
situation 2, case 2 (figure 3, induction hypothesis). For nodes of $0331$_PQT_
k-3 are embedded into $10$_CQ_ l-2 and $00$_CQ_ l-2 such that:

  * 1.

$0$_$33$ suff_1 is embedded into the same parent component ($10$_CQ_ l-2)
using _f_ (figure 1, induction hypothesis);

  * 2.

$0$_$331$ suff_1 is embedded into the same parent component ($10$_CQ_ l-2)
using _f_ 1 of situation 2, case 3 (figure 4, induction hypothesis);

  * 3.

nodes $0$_$331$ suff_2 or $0$_$331$ suff_3 are embedded into $00$_CQ_ l-2 by
definition 02 using _f_ 1 of situation 2, case 3 (figure 4).

For nodes of $0332$_PQT_ k-3 are embedded into $11$_CQ_ l-2 and $01$_CQ_ l-2
such that:

  * 1.

$0$_$33$ suff_2 is embedded into $11$_CQ_ l-2 of $1$_CQ_ l-1 using _f_ (figure
1, induction hypothesis);

  * 2.

nodes $0$_$332$ suff_1 or $0$_$332$ suff_2 are embedded into the same parent
component ($11$_CQ_ l-2) using _f_ 1 of situation 2, case 3 (figure 4,
induction hypothesis);

  * 3.

node $0$_$332$ suff_3 is embedded into $01$_CQ_ l-2 of $0$_CQ_ l-1 by
definition 02 using _f_ 1 situation 2, case 3 (figure 4).

For nodes of $0333$_PQT_ k-3 are embedded into $11$_CQ_ l-2 and $01$_CQ_ l-2
such that:

  * 1.

$0$_$33$ suff_3 is embedded into $11$_CQ_ l-2 of $1$_CQ_ l-1 using _f_ (figure
1, induction hypothesis);

  * 2.

nodes $0$_$333$ suff_1 or $0$_$333$ suff_2 are embedded into the same parent
component ($11$_CQ_ l-2) using _f_ 1 of situation 2, case 3 (figure 4,
induction hypothesis);

  * 3.

node $0$_$333$ suff_3 is embedded $01$_CQ_ l-2 of $0$_CQ_ l-1 by definition 02
using _f_ 1 of situation 2, case 3 (figure 4).

Theorem 1. For $n>5$, a particular sub-quadtree _PQT n_ is one-by-one vertex
embedding into $m$-dimensional crossed cubes _CQ_ m.
Proof. We prove theorem 1 by induction on $n$.
Base. For $n=6,8$: level’s 1, 2 nodes of _PQT_ 6, _PQT_ 8 respectively are
embedded using the rules specified in table 4 and table 5.

_Root_ | _Prem(root)_ |  $0$_suff_ 1 |  _pref 1CQ_4
---|---|---|---
${\color[rgb]{0,0,1}0}$ | ${\color[rgb]{1,0,0}00000}0000$ | $0{\color[rgb]{0,0,1}1}$ | ${\color[rgb]{1,0,0}01000}0000$
$0$_suff_ 2 |  _pref 2CQ_4 |  $0$_suff_ 3 |  _pref 3CQ_4
$0{\color[rgb]{0,0,1}2}$ | ${\color[rgb]{1,0,0}10000}0000$ | $0{\color[rgb]{0,0,1}3}$ | ${\color[rgb]{1,0,0}11000}0000$

Table 4: Level’s 1, 2 nodes embedding of _PQT_ 6 into _CQ_ 9.

_Root_ | _Prem(root)_ |  $0$_suff_ 1 |  $0$_pref 1CQ_4
---|---|---|---
${\color[rgb]{0,0,1}0}$ | ${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}0000000}0000$ | $0{\color[rgb]{0,0,1}1}$ | ${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}0100000}0000$
$0$_suff_ 2 |  $1$_pref 1CQ_4 |  $0$_suff_ 3 |  $1$_pref 0CQ_4
$0{\color[rgb]{0,0,1}2}$ | ${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}0100000}0000$ | $0{\color[rgb]{0,0,1}3}$ | ${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}0000000}0000$

Table 5: Level’s 1, 2 nodes embedding of _PQT_ 8 into _CQ_ 12.

Induction hypothesis

Suppose that for $k\leq n-1$, _PQT_ k is one-by-one vertex embedding into _CQ_
l with $l<m$ is true.
Let us now prove that it is true for $k=n$.
There are two cases:
Case a: $C=\phi$

One-by-one vertex embedding of $01$_PQT_ k-1, $02$_PQT_ k-1, $03$_PQT_ k-1,
and $0$_PQT_ k respectively into $01$_CQ_ l-2, $10$_CQ_ l-2, $11$_CQ_ l-2, and
$00$_CQ_ l-2; in this case, we use the same actions as lemma 1.
Case b: $C\neq\phi$

One-by-one vertex embedding of $01$_PQT_ k-1, $02$_PQT_ k-1, $03$_PQT_ k-1,
and $0$_PQT_ k respectively into $0$_CQ_ l-1, $1$_CQ_ l-1, $0$_CQ_ l-1 and
$1$_CQ_ l-1, and the root $0$ into $00$_CQ_ l-2; in this case, we use the same
actions as lemma 2 except the sub-_PQT_ : $0111$_PQT_ k-3, $0311$_PQT_ k-3,
and $0321$_PQT_ k-3 are embedded as situation 2, case 1, b as shown in figure
2.

###  3.3 Dilation two one-by-one edges embedding

Dilation two one-by-one edges embedding of _PQT_ n onto _CQ_ m is done in the
following way:
For $n=3$: the basic function _R_ of this dilation two one-by-one edges
embedding is produced as follows:

  * 1.

_R(A p-1-Ap-1suff1) := Pref0$00$-Pref1$00$_

  * 2.

_R(A p-1-Ap-1suff2) := Pref0$00$-Pref2$00$ _

  * 3.

_R(A p-1-Ap-1suff3) := Pref0$00$-Pref2$00$-Pref3$00$_

For $n>3$: dilation two one-by-one edges embedding is done by two situations.
In the first, there are two cases; the first case is when $C=\phi$, we use the
basic function _R_ ; an example is shown in figure 9.

Figure 9: Edges embedding situation 1, case 1.

The second case is when $C\neq\phi$, and we only use one copy $b_{0}$_CQ_ m-1
or $\bar{b}_{0}$_CQ_ m-1; the second case is shown in figures 9 and 10. _R_ is
produced like situation 1, case 1, or as follows:

  * 1.

_R(a p-1-Ap-1suff1) := Pref1$00X$-Pref1$00Y$ _

  * 2.

_R(A p-1-Ap-1suff2) := Pref1$00X$-Pref3$00Y$
-Pref2$00Z$_

  * 3.

_R(A p-1-Ap-1suff3) := Pref1$00X$-Pref3$00Y$ _

Figure 10: Edges embedding situation 1, case 2.

The second situation is when $C\neq\phi$; in this situation, we use the two
copies $b_{0}$_CQ_ m-1 and $\bar{b}_{0}$_CQ_ m-1; a function _R_ 1 of this
dilation two one-by-one edges embedding. There are three cases; the first is
shown in figure 11. The following rules of case 1 produce _R_ 1:

  * 1.

_R 1(Ap-1-Ap-1suff1) := $0$Pref0$00X$-$0$Pref1$00Y$_

  * 2.

_R 1(Ap-1-Ap-1suff2) := $0$Pref0$00X$-$0$Pref1$00Y$
-$1$Pref1$00Z$_

  * 3.

_R 1(Ap-1-Ap-1suff3) := $0$Pref0$00X$-$1$Pref0$00Y$_

OR

  * 1.

_R 1(Ap-1-Ap-1suff1) := $\bar{0}$Pref0$00X$-$\bar{0}$Pref1$00Y$_

  * 2.

_R 1(Ap-1-Ap-1suff2) := $\bar{0}$Pref0$00X$-$\bar{0}$Pref1$00Y$
-$\bar{1}$Pref1$00Z$_

  * 3.

_R 1(Ap-1-Ap-1suff3) := $\bar{0}$Pref0$00X$-$1$Pref0$00Y$_

The following rules of case 2 shown in figure 12 produce _R_ 1:

  * 1.

_R 1(Ap-1-Ap-1suff1) := $\bar{0}$Pref0$00X$-$\bar{0}$Pref0$00Y$_

  * 2.

_R 1(Ap-1-Ap-1suff2) := $\bar{0}$Pref0$00X$-$\bar{0}$Pref0$00Y$
-$\bar{1}$Pref0$00Z$_

  * 3.

_R 1(Ap-1-Ap-1suff3) := $\bar{0}$Pref0$00X$-$1$Pref0$00Y$_

OR

  * 1.

_R 1(Ap-1-Ap-1suff1) := $\bar{0}$Pref0$00X$-$\bar{0}$Pref0$00Y$_

  * 2.

_R 1(Ap-1-Ap-1suff2) := $\bar{0}$Pref0$00X$-$\bar{1}$Pref0$00Y$_

  * 3.

_R 1(Ap-1-Ap-1suff3) := $\bar{0}$Pref0$00X$-$1$Pref0$00Y$
-$1$Pref0$00Z$ _

Figure 11: Edges embedding situation 2, case 1. Figure 12: Edges embedding
situation 2, case 2.

The following rules of the last case shown in figure 13 produce _R_ 1 ($t$ $=$
2, 3):

  * 1.

_R 1(Ap-1-Ap-1suff1) := $\bar{0}$Pref1$00X$-$\bar{0}$Pref1$00Y$_

  * 2.

_R 1(Ap-1-Ap-1suff2) := $\bar{0}$Pref0+1$00X$-$\bar{1}$Pref1$00Y$_

  * 3.

_R 1(Ap-1-Ap-1suff3) := $\bar{0}$Pref1$00X$-$0$Pref1$00Y$
-$\bar{1}$Pref1$00Z$_

OR

  * 1.

_R 1(Ap-1-Ap-1suff1) := $\bar{0}$Preft$00X$\-
$\bar{0}$Preft$00Y$_

  * 2.

_R 1(Ap-1-Ap-1suff2) := $\bar{0}$Preft$00X$-$\bar{0}$Preft$00Y$\-
$1$Pref1$00Z$_

  * 3.

_R 1(Ap-1-Ap-1suff3) := $\bar{0}$Pref0$00X$-$\bar{1}$Preft$00Y$ _

OR

  * 1.

_R 1(Ap-1-Ap-1suff1) := $\bar{0}$Pref2$00X$-$\bar{0}$Pref2)$00Y$_

  * 2.

_R 1(Ap-1-Ap-1suff2) := $\bar{0}$Pref2$00X$-$1$Pref2$00Y$_

  * 3.

_R 1(Ap-1-Ap-1suff3) := $\bar{0}$Pref2$00X$-$\bar{1}$Pref2$00Y$ _

Figure 13: Edges embedding situation 2, case 3.

Lemma 3. For any $n<5$, a particular sub-quadtree _PQT n_ of dimension _n_ is
dilation two one-by-one edges embedding onto $m$-dimensional crossed cubes
_CQ_ m.
Proof. We prove lemma 3 by induction on $n$.
Base. For $n=\overline{2,4}$: edges between vertices of level 1 and level 2 of
_PQT_ n are embedded using the rules specified in table 6.

|  _PQT_ edge | crossed cubes path | Dilation
---|---|---|---
$n=2$ |  _${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}1}$_ |  _$00$_ -_$01$_ | 1
_${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}2}$_ |  _$00$_ -_$10$_ | 1
_${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}3}$_ |  _$00$_ -_$10$_ -_$11$_ | 2
$n=3$ |  _${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}1}$_ |  _${\color[rgb]{1,0,0}00}00$_ -_${\color[rgb]{1,0,0}01}00$_ | 1
_${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}2}$_ |  _${\color[rgb]{1,0,0}00}00$_ -_${\color[rgb]{1,0,0}10}00$_ | 1
_${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}3}$_ |  _${\color[rgb]{1,0,0}00}00$_ -_${\color[rgb]{1,0,0}10}00$_ -_${\color[rgb]{1,0,0}11}00$_ | 2
$n=4$ |  _${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}1}$_ |  _${\color[rgb]{1,0,0}00}0000$_ -_${\color[rgb]{1,0,0}01}0000$_ | 1
_${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}2}$_ |  _${\color[rgb]{1,0,0}00}0000$_ -_${\color[rgb]{1,0,0}10}0000$_ | 1
_${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}3}$_ |  _${\color[rgb]{1,0,0}00}0000$_ -_${\color[rgb]{1,0,0}10}0000$_ -_${\color[rgb]{1,0,0}11}0000$_ | 2

Table 6: Edges embedding between vertex of level 1 and level 2 of _PQT_ 2,
_PQT_ 3, _PQT_ 4.

Induction hypothesis

Suppose that for $k\leq n-1$, _PQT_ k is dilation two one-by-one edges
embedding onto _CQ_ l with $l<m$ is true.
Is it true for $k=n$ ?.

Edges between the root $0$ and $01$_PQT_ k-1, $02$_PQT_ k-1, and $03$_PQT_ k-1
are embedded respectively onto paths between $00$_CQ_ l-2 and $01$_CQ_ l-2,
$00$_CQ_ l-2 and $10$_CQ_ l-2, and $00$_CQ_ l-2 and $10$_CQ_ l-2 and $11$_CQ_
l-2. Edges in this lemma are embedded using _R_ (induction hypothesis,
situation 1, case 1, as shown in figure 9).

Lemma 4. For any $n\geq 5$, all edges in the same sub-_PQT 5_ of any _PQT n_
is dilation two one-by-one edges embedding onto paths in the same sub-_CQ_ 7
of any supernode of _CQ_ m.
Proof. We prove lemma 4 by induction on $n$.
Base. For $n=5$: edges of _PQT_ 5 are embedded using the rules specified in
table 7.

|  _PQT_ edge | crossed cubes path | Dilation
---|---|---|---
A |  _${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}1}$_ |  _${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}00}0000$_ -_${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}01}0000$_ | 1
_${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}2}$_ |  _${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}00}0000$_ -_${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}01}0000$_ -_${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}01}0000$_ | 2
_${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}3}$_ |  _${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}00}0000$_ -_${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}00}0000$_ | 1
B |  _$0{\color[rgb]{0,0,1}1}$_ -_$01{\color[rgb]{0,0,1}1}$_ |  _${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}01}0000$_ -_${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}01}0001$_ | 1
_$0{\color[rgb]{0,0,1}1}$_ -_$01{\color[rgb]{0,0,1}2}$_ |  _${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}01}0000$_ -_${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}11}0000$_ -_${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}10}0000$_ | 2
_$0{\color[rgb]{0,0,1}1}$_ -_$01{\color[rgb]{0,0,1}3}$_ |  _${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}01}0010$_ -_${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}11}0000$_ | 1
C |  _$0{\color[rgb]{0,0,1}3}$_ -_$03{\color[rgb]{0,0,1}1}$_ |  _${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}00}0000$_ -_${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}00}0001$_ | 1
_$0{\color[rgb]{0,0,1}3}$_ -_$03{\color[rgb]{0,0,1}2}$_ |  _${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}00}0000$_ -_${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}00}0001$_ -_${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}00}0011$_ | 2
_$0{\color[rgb]{0,0,1}3}$_ -_$03{\color[rgb]{0,0,1}3}$_ |  _${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}00}0000$_ -_${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}00}0010$_ | 1
D |  _$033{\color[rgb]{0,0,1}1}$_ -_$0331{\color[rgb]{0,0,1}1}$_ |  _${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}01}0010$_ -_${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}01}0011$_ | 1
_$033{\color[rgb]{0,0,1}1}$_ -_$0331{\color[rgb]{0,0,1}2}$_ |  _${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}01}0010$_ -_${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}01}0010$_ | 1
_$033{\color[rgb]{0,0,1}1}$_ -_$0331{\color[rgb]{0,0,1}3}$_ |  _${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}01}0010$_ -_${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}01}0010$_ -_${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}01}0011$_ | 2

Table 7: Edges embedding of _PQT_ 5 into _CQ_ 7, A: example of situation 2,
case 1; B: example of situation 1, case 2; C: example of situation 2, case 2;
D: example of situation 2, case 3.

Induction hypothesis

Suppose that for $k\leq n-1$, any sub-_PQT 5_ of _PQT k_ is dilation two one-
by-one edges embedding onto any sub-_CQ_ 7 of _CQ_ l with $l<m$ is true.
Is it true for $k=n$ ?.

For any sub-_PQT_ ${}_{k^{{}^{\prime}}}$, sub-_CQ_ ${}_{l^{{}^{\prime}}}$ with
$k^{{}^{\prime}}=5$, $l^{{}^{\prime}}=7$; the edge between $0$_PQT_
${}_{k^{{}^{\prime}}}$, $01$_PQT_ ${}_{k^{{}^{\prime}}-1}$ is embedded onto a
path in the same component $00$_CQ_ ${}_{l^{{}^{\prime}}-2}$ using _R_ 1 of
situation 2, case 1 (figure 11, induction hypothesis). For edges of $01$_PQT_
${}_{k^{{}^{\prime}}-1}$ are embedded onto paths between $00$_CQ_
${}_{l^{{}^{\prime}}-2}$, $01$_CQ_ ${}_{l^{{}^{\prime}}-2}$, and the same
$00$_CQ_ ${}_{l^{{}^{\prime}}-2}$, $01$_CQ_ ${}_{l^{{}^{\prime}}-2}$ of
$0$_CQ_ ${}_{l^{{}^{\prime}}-1}$ using _R_ (figures 9, 10, induction
hypothesis).

The edge between $0$_PQT_ ${}_{k^{{}^{\prime}}}$, $02$_PQT_
${}_{k^{{}^{\prime}}-1}$ is embedded onto a path in the same component
$00$_CQ_ ${}_{l^{{}^{\prime}}-2}$ (induction hypothesis), and between $00$_CQ_
${}_{l^{{}^{\prime}}-2}$, $10$_CQ_ ${}_{l^{{}^{\prime}}-2}$ by definition 02
using _R_ 1 of situation 2, case 1 (figure 11). For edges of $02$_PQT_
${}_{k^{{}^{\prime}}-1}$ are embedded onto paths between $10$_CQ_
${}_{l^{{}^{\prime}}-2}$, $11$_CQ_ ${}_{l^{{}^{\prime}}-2}$, and the same
$10$_CQ_ ${}_{l^{{}^{\prime}}-2}$, $11$_CQ_ ${}_{l^{{}^{\prime}}-2}$ of
$1$_CQ_ ${}_{l^{{}^{\prime}}-1}$ using _R_ (figures 9, 10, induction
hypothesis).

The edge between $0$_PQT_ ${}_{k^{{}^{\prime}}}$, $03$_PQT_
${}_{k^{{}^{\prime}}-1}$ is embedded onto a path between $00$_CQ_
${}_{l^{{}^{\prime}}-2}$, $10$_CQ_ ${}_{l^{{}^{\prime}}-2}$ by definition 02
using _R_ 1 of situation 2, case 1 (figure 11). For edges of $03$_PQT_
${}_{k^{{}^{\prime}}-1}$ are embedded as follows: the edge between $03$_PQT_
${}_{k^{{}^{\prime}}-1}$, $031$_PQT_ ${}_{k^{{}^{\prime}}-2}$ is embedded onto
a path in the same component $10$_CQ_ ${}_{l^{{}^{\prime}}-2}$ using _R_ 1 of
situation 2, case 2 (figure 12, induction hypothesis); the edge between
$03$_PQT_ ${}_{k^{{}^{\prime}}-1}$, $032$_PQT_ ${}_{k^{{}^{\prime}}-2}$ is
embedded onto a path in the same component $10$_CQ_ ${}_{l^{{}^{\prime}}-2}$
(induction hypothesis), and between $10$_CQ_ ${}_{l^{{}^{\prime}}-2}$,
$00$_CQ_ ${}_{l^{{}^{\prime}}-2}$ by definition 02 using _R_ 1 of situation 2,
case 2 (figure 12). Edges of $031$_PQT_ ${}_{k^{{}^{\prime}}-2}$, $032$_PQT_
${}_{k^{{}^{\prime}}-2}$ are embedded onto paths in the same $00$_CQ_
${}_{l^{{}^{\prime}}-2}$, $10$_CQ_ ${}_{l^{{}^{\prime}}-2}$ using _R_ of
situation 1, case 1(figure 9, induction hypothesis).

The edge between $03$_PQT_ ${}_{k^{{}^{\prime}}-1}$, $033$_PQT_
${}_{k^{{}^{\prime}}-2}$ is embedded onto a path in the same component
$10$_CQ_ ${}_{l^{{}^{\prime}}-2}$ using _R_ 1 of situation 2, case 2 (figure
12, induction hypothesis). For edges of $033$_PQT_ ${}_{k^{{}^{\prime}}-2}$
are embedded as follows: the edge between $033$_PQT_ ${}_{k^{{}^{\prime}}-2}$,
$0331$_PQT_ ${}_{k^{{}^{\prime}}-3}$ is embedded onto a path in the same
component $10$_CQ_ ${}_{l^{{}^{\prime}}-2}$ using _R_ of situation 1, case 1
(figure 9, induction hypothesis). Edges of $0331$_PQT_
${}_{k^{{}^{\prime}}-3}$ are embedded onto paths in the same component
$10$_CQ_ ${}_{l^{{}^{\prime}}-2}$ (induction hypothesis), between $10$_CQ_
${}_{l^{{}^{\prime}}-2}$, $00$_CQ_ ${}_{l^{{}^{\prime}}-2}$ by definition 02 ,
and in the same component $00$_CQ_ ${}_{l^{{}^{\prime}}-2}$ (induction
hypothesis) using _R_ 1 of situation 2, case 3 (figure 13).

Edges between $033$_PQT_ ${}_{k^{{}^{\prime}}-2}$, $0332$_PQT_
${}_{k^{{}^{\prime}}-3}$ or $0333$_PQT_ ${}_{k^{{}^{\prime}}-3}$ are embedded
onto paths between $10$_CQ_ ${}_{l^{{}^{\prime}}-2}$, $11$_CQ_
${}_{l^{{}^{\prime}}-2}$ of $1$_CQ_ ${}_{l^{{}^{\prime}}-1}$ using _R_ of
situation 1, case 1 (figure 9, induction hypothesis).

Edges of $0332$_PQT_ ${}_{k^{{}^{\prime}}-3}$ or $0333$_PQT_
${}_{k^{{}^{\prime}}-3}$ are embedded onto paths in the same component
$11$_CQ_ ${}_{l^{{}^{\prime}}-2}$ (induction hypothesis), and between $11$_CQ_
${}_{l^{{}^{\prime}}-2}$, $01$_CQ_ ${}_{l^{{}^{\prime}}-2}$ by definition 02
using _R_ 1 of situation 2, case 3 (figure 13).

Theorem 2. For any $n>5$, a particular sub-quadtree _PQT n_ is dilation two
one-by-one edges embedding onto $m$-dimensional crossed cubes _CQ_ m.
Proof. We prove theorem 2 by induction on $n$.
Base. For $n=6,8$: edges of _PQT_ 6, _PQT_ 8 are respectively embedded using
the rules specified in table 8, table 9.

_PQT_ edge | crossed cubes path | Dilation
---|---|---
_${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}1}$_ |  _${\color[rgb]{1,0,0}00000}0000$_ -_${\color[rgb]{1,0,0}01000}0000$_ | 1
_${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}2}$_ |  _${\color[rgb]{1,0,0}00000}0000$_ -_${\color[rgb]{1,0,0}10000}0000$_ | 1
_${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}3}$_ |  _${\color[rgb]{1,0,0}00000}0000$_ -_${\color[rgb]{1,0,0}10000}0000$_ -_${\color[rgb]{1,0,0}11000}0000$_ | 2

Table 8: Edges embedding of _PQT_ 6 into _CQ_ 9.

Induction hypothesis

Suppose that for $k\leq n-1$, _PQT_ k is dilation two one-by-one edges
embedding onto _CQ_ l with $l<m$ is true.
Is it true for $k=n$ ?.
There are two cases:
Case a: $C=\phi$

Dilation two one-by-one edges embedding between the root $0$ and respectively
$01$_PQT_ k-1, $02$_PQT_ k-1, and $03$_PQT_ k-1 onto paths respectively
between $00$_CQ_ l-2 and $01$_CQ_ l-2, $00$_CQ_ l-2 and $10$_CQ_ l-2, $00$_CQ_
l-2 and $11$_CQ_ l-2. In this case, we use the same actions as lemma 3.
Case b: $C\neq\phi$

Dilation two one-by-one edges embedding between the root $0$ and respectively
$01$_PQT_ k-1, $02$_PQT_ k-1, and $03$_PQT_ k-1 onto paths in the same
supernode $00$_CQ_ l-2, and between $00$_CQ_ l-2, $10$_CQ_ l-2 (situation 2,
case 1, a figure 11). Dilation two one-by-one edges of $01$_PQT_ k-1,
$02$_PQT_ k-1, and $03$_PQT_ k-1 respectively onto paths in $0$_CQ_ l-1,
$1$_CQ_ l-1, and both $0$_CQ_ l-1, $1$_CQ_ l-1.

In this case, we use the same actions as lemma 4 except the edges of sub-_PQT_
: $0111$_PQT_ k-3, $0311$_PQT_ k-3, and $0321$_PQT_ k-3 are embedded like
situation 2, case 1, b (figure 11). Moreover, edges of sub-_PQT_ :
$01113$_PQT_ k-4, $03113$_PQT_ k-4, and $03213$_PQT_ k-4 are embedded as
situation 2, case 2, b (figure 12).

|  _PQT_ edge | crossed cubes path | Dilation
---|---|---|---
A |  _${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}1}$_ |  _${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}0000000}0000$_ -_${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}0100000}0000$_ |  1
_${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}2}$_ |  _${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}0000000}0000$_ -_${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}0100000}0000$_ -_${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}0100000}0000$_ |  2
_${\color[rgb]{0,0,1}0}$_ -_$0{\color[rgb]{0,0,1}3}$_ |  _${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}0000000}0000$_ -_${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}0000000}0000$_ |  1
B |  _$0{\color[rgb]{0,0,1}3}$_ -_$03{\color[rgb]{0,0,1}1}$_ |  _${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}0000000}0000$_ -_${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}0001000}0000$_ |  1
_$0{\color[rgb]{0,0,1}3}$_ -_$03{\color[rgb]{0,0,1}2}$_ |  _${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}0000000}0000$_ - _${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}0001000}0000$_ -_${\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}0001000}0000$_ |  2
_$0{\color[rgb]{0,0,1}3}$_ -_$03{\color[rgb]{0,0,1}3}$_ |  _${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}0000000}0000$_ -_${\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}0000000}0001$_ |  1
C |  _$0{\color[rgb]{0,0,1}1}$_ -_$01{\color[rgb]{0,0,1}1}$_ |  _${\color[rgb]{1,0.39,0.13}0}{\color[rgb]{1,0,0}0100000}0000$_ -_${\color[rgb]{1,0.39,0.13}0}{\color[rgb]{1,0,0}0101000}0000$_ |  1
_$0{\color[rgb]{0,0,1}1}$_ -_$01{\color[rgb]{0,0,1}2}$_ |  _${\color[rgb]{1,0.39,0.13}0}{\color[rgb]{1,0,0}0100000}0000$_ - _${\color[rgb]{1,0.39,0.13}0}{\color[rgb]{1,0,0}1100000}0000$_ -_${\color[rgb]{1,0.39,0.13}0}{\color[rgb]{1,0,0}1000000}0000$_ |  2
_$0{\color[rgb]{0,0,1}1}$_ -_$01{\color[rgb]{0,0,1}3}$_ |  _${\color[rgb]{1,0.39,0.13}0}{\color[rgb]{1,0,0}0100000}0000$_ -_${\color[rgb]{1,0.39,0.13}0}{\color[rgb]{1,0,0}1100000}0000$_ |  1
D |  _$01{\color[rgb]{0,0,1}1}$_ -_$011{\color[rgb]{0,0,1}1}$_ |  _${\color[rgb]{1,0.39,0.13}001}{\color[rgb]{1,0,0}01000}0000$_ -_${\color[rgb]{1,0.39,0.13}001}{\color[rgb]{1,0,0}01100}0000$_ |  1
_$01{\color[rgb]{0,0,1}1}$_ -_$011{\color[rgb]{0,0,1}2}$_ |  _${\color[rgb]{1,0.39,0.13}001}{\color[rgb]{1,0,0}01000}0000$_ - _${\color[rgb]{1,0.39,0.13}001}{\color[rgb]{1,0,0}11000}0000$_ -_${\color[rgb]{1,0.39,0.13}001}{\color[rgb]{1,0,0}10000}0000$_ |  2
_$01{\color[rgb]{0,0,1}1}$_ -_$011{\color[rgb]{0,0,1}3}$_ |  _${\color[rgb]{1,0.39,0.13}001}{\color[rgb]{1,0,0}01000}0000$_ -_${\color[rgb]{1,0.39,0.13}001}{\color[rgb]{1,0,0}11000}0000$_ |  1
E |  _$011{\color[rgb]{0,0,1}1}$_ -_$0111{\color[rgb]{0,0,1}1}$_ |  _${\color[rgb]{1,0.39,0.13}00101}{\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}00}0000$_ -_${\color[rgb]{1,0.39,0.13}00101}{\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}01}0000$_ |  1
_$011{\color[rgb]{0,0,1}1}$_ -_$0111{\color[rgb]{0,0,1}2}$_ |  _${\color[rgb]{1,0.39,0.13}00101}{\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}00}0000$_ - _${\color[rgb]{1,0.39,0.13}00101}{\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}01}0000$_ -_${\color[rgb]{1,0.39,0.13}00101}{\color[rgb]{0,0.88,0}0}{\color[rgb]{1,0,0}01}0000$_ |  2
_$011{\color[rgb]{0,0,1}1}$_ -_$0111{\color[rgb]{0,0,1}3}$_ |  _${\color[rgb]{1,0.39,0.13}00101}{\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}00}0000$_ -_${\color[rgb]{1,0.39,0.13}00101}{\color[rgb]{0,0.88,0}1}{\color[rgb]{1,0,0}00}0001$_ |  1

Table 9: Edges embedding of _PQT_ 8 into _CQ_ 12, A: example of situation 2,
case 1; B: example of situation 2, case 2; C, D: example of situation 1, case
2; E: example of situation 2, case 1.

##  4 Conclusion

In this paper, we have proposed a new function for embedding _PQT_ n into _CQ_
m. The main purpose is dilation two one-by-one embedding _PQT_ n into _CQ_ m.
The study of dilation of this function is explained in three steps. The first
step is dilation two one-by-one embeddings all edges onto paths in the same
_CQ_ 4 of any supernode of _CQ_ m as proved by lemma 3. The second step is
dilation two one-by-one embeddings all edges onto paths in the same _CQ_ 7 of
any supernode of _CQ_ m as proved by lemma 4. The third step is the general
dilation two one-by-one embeddings all edges of _PQT_ n onto paths between two
supernodes of _CQ_ m as proved by theorem 2.
As a perspective, it is more interesting to study the fault-tolerant embedding
of _PQT_ n into _CQ_ m.

## CRediT authorship contribution statement

Selmi Aymen Takie eddine: ConceptuaIization, Writing- original draft, Writing-
review & editing, Investigation. Mohamed Faouzi Zerarka: Conceptualization,
Writing–review & editing. Abdelhakim Cheriet: Conceptualization.

## Declaration of competing interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## Acknowledgment

This work was funded in part by the Algerian Ministry of Higher Education and
Scientific Research under contrat PRFU C00L07UN070120210004.

## References

  * Zhou et al. [2020] J. Zhou, J. Ben, R. Wang, M. Zheng, L. Du,  Lattice quad-tree indexing algorithm for a hexagonal discrete global grid system,  ISPRS International Journal of Geo-Information 9 (2020) 83.
  * Shukla et al. [2020] P. Shukla, A. Verma, S. Verma, M. Kumar, et al.,  Interpreting svm for medical images using quadtree,  Multimedia Tools and Applications 79 (2020) 29353–29373.
  * Banerjee et al. [2020] S. Banerjee, Z. W. Wang, H. H. Chopp, O. Cossairt, A. Katsaggelos,  Quadtree driven lossy event compression,  arXiv preprint arXiv:2005.00974 (2020).
  * Shen and Zhao [2020] Q. Shen, Y. Zhao,  Perceptual hashing for color image based on color opponent component and quadtree structure,  Signal Processing 166 (2020) 107244.
  * Albani et al. [2021] D. Albani, W. Hönig, D. Nardi, N. Ayanian, V. Trianni,  Hierarchical task assignment and path finding with limited communication for robot swarms,  Applied Sciences 11 (2021) 3115.
  * Efe and Fernández [1996] K. Efe, A. Fernández,  Mesh-connected trees: a bridge between grids and meshes of trees,  IEEE Transactions on Parallel and Distributed Systems 7 (1996) 1281–1291.
  * Rabie and Kamel [2017] T. Rabie, I. Kamel,  Toward optimal embedding capacity for transform domain steganography: a quad-tree adaptive-region approach,  Multimedia Tools and Applications 76 (2017) 8627–8650.
  * Jaillet and Lobos [2021] F. Jaillet, C. Lobos,  Fast quadtree/octree adaptive meshing and re-meshing with linear mixed elements,  Engineering with Computers (2021) 1–18.
  * Gupta et al. [2003] A. K. Gupta, D. Nelson, H. Wang,  Efficient embeddings of ternary trees into hypercubes,  Journal of Parallel and Distributed Computing 63 (2003) 619–629.
  * Abuelrub [2010] E. Abuelrub,  Embedding interconnection networks in crossed cubes,  in: Electronic Engineering and Computing Technology, Springer, 2010, pp. 141–151.
  * Leighton [1991] F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Array, Trees, Hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1991.
  * Barasch et al. [1989] L. Barasch, S. Lakshmivarahan, S. Dhall,  Embedding arbitrary meshes and complete binary trees in generalized hypercubes,  in: Proceedings of the 1st IEEE Symposium on Parallel and Distributed Processing, pp. 202–209.
  * Keh and Lin [2000] H.-C. Keh, J.-C. Lin,  On fault-tolerant embedding of hamiltonian cycles, linear arrays and rings in a flexible hypercube,  Parallel Comput. 26 (2000) 769–781.
  * Youyao et al. [2008] L. Youyao, H. Jungang, D. Huimin,  A hypercube-based scalable interconnection network for massively parallel computing,  Journal of Computers (2008).
  * Pai [2020] K.-j. Pai,  A parallel algorithm for constructing two edge-disjoint hamiltonian cycles in crossed cubes,  in: International Conference on Algorithmic Applications in Management, Springer, pp. 448–455.
  * Yang [2021] Y. Yang,  Embedded connectivity of ternary n-cubes,  Theoretical Computer Science (2021).
  * El-Amawy and Latifi [1991] A. El-Amawy, S. Latifi,  Properties and performance of folded hypercubes,  IEEE Trans. Parallel Distrib. Syst. 2 (1991) 31–42.
  * Preparata and Vuillemin [1981] F. P. Preparata, J. Vuillemin,  The cube-connected cycles: A versatile network for parallel computation,  Commun. ACM 24 (1981) 300–309.
  * Efe [1992] K. Efe,  The crossed cube architecture for parallel computation,  IEEE Trans. Parallel Distrib. Syst. 3 (1992) 513–524.
  * Abuelrub [2008] E. Abuelrub,  The hamiltonicity of crossed cubes in the presence of faults,  Eng. Lett. 16 (2008) 453–459.
  * Chang et al. [2000] C.-P. Chang, T.-Y. Sung, L.-H. Hsu,  Edge congestion and topological properties of crossed cubes,  IEEE Transactions on Parallel and Distributed Systems 11 (2000) 64–80.
  * Fan et al. [2005] J. Fan, X. Lin, X. Jia,  Node-pancyclicity and edge-pancyclicity of crossed cubes,  Information Processing Letters 93 (2005) 133–138.
  * Zhu et al. [2007] Q. Zhu, J.-M. Xu, X. Hou, M. Xu,  On reliability of the folded hypercubes,  Information Sciences 177 (2007) 1782–1788.
  * Kulasinghe and Bettayeb [1995] P. Kulasinghe, S. Bettayeb,  Multiply-twisted hypercube with five or more dimensions is not vertex-transitive,  Information Processing Letters 53 (1995) 33–36.
  * Wang et al. [2021] X. Wang, J. Fan, S. Zhang, J. Yu,  Node-to-set disjoint paths problem in cross-cubes,  The Journal of Supercomputing (2021) 1–25.
  * Cheng et al. [2017] B. Cheng, D. Wang, J. Fan,  Constructing completely independent spanning trees in crossed cubes,  Discrete Applied Mathematics 219 (2017) 100–109.
  * Pai et al. [2020] K.-J. Pai, R.-S. Chang, R.-Y. Wu, J.-M. Chang,  Three completely independent spanning trees of crossed cubes with application to secure-protection routing,  Information Sciences 541 (2020) 516–530.
  * Dong et al. [2012] Q. Dong, J. Zhou, Y. Fu, X. Yang,  Embedding a mesh of trees in the crossed cube,  Information Processing Letters 112 (2012) 599–603.
  * Kulasinghe and Bettayeb [1995] P. Kulasinghe, S. Bettayeb,  Embedding binary trees into crossed cubes,  IEEE Transactions on Computers 44 (1995) 923–929.
  * Aschheim et al. [2012] R. Aschheim, S. Femmam, M. F. Zerarka,  New "graphiton" model: a computational discrete space, self-encoded as a trivalent graph,  Comput. Inf. Sci. 5 (2012) 2–12.
  * Lin et al. [2010] J.-C. Lin, J.-S. Yang, C.-C. Hsu, J.-M. Chang,  Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes,  Information Processing Letters 110 (2010) 414–419.
  * Femmam and Zerarka [2017] S. Femmam, F. M. Zerarka,  One-by-one embedding of the twisted hypercube into pancake graph,  in: Building Wireless Sensor Networks, Elsevier, 2017, pp. 145–169.
  * Matsubayashi [2015] A. Matsubayashi,  Separator-based graph embedding into multidimensional grids with small edge-congestion,  Discrete Applied Mathematics 185 (2015) 119–137.

Aymen Takie Eddine Selmi: is a PhD student in University of Biskra, Algeria.
He obtained a master degree in systems information, decision and optimization
in 2018 from University of Biskra.His current research interests include
parallel computing, optimization, and machine learning.

Mohamed Faouzi Zerarka: received Magister and PhD. Degrees in computer
sciences department of computer sciences from university of Biskra, Algeria.
He worked for a number of years in university of Batna Algeria, currently he
is associate professor at Biskra university, Algeria, with expertise in
parallel architecture and computing.

Abdelhakim Cheriet: received the Engineering, M.Sc. and PhD degrees in 2004,
2008, and 2016 from the University of Biskra, Algeria, all in Computer
Science. He worked as an assistant professor at the University of Biskra,
Algeria until 2016. Currently, he is an associate professor at the University
of Ouargla, Algeria. His research interests include: Optimization,
Metaheuristics, and Evolutionary Computation.