Applied Mathematics, 2010, 3, 499-503
doi:10.4236/am.2010.16065 Published Online December 2010 (http://www.SciRP.org/journal/am)
On Embedding of m-Sequential k-ary
Trees into Hypercubes*
Indra Rajasingh, Bharati Rajan, Ramanathan Sundara Rajan
Department of Mat hematics, Loyola College, Chennai, India
Received June 25, 2010; revised October 12, 2010; accepted October 18, 2010
Abstract
In this paper, we present an algorithm for embedding an m-sequential k-ary tree into its optimal hypercube
with dilation at most 2 and prove its correctness.
Keywords: Hypercube, Embedding, Dilation, Pre-order Labeling, Hamiltonian Cycle, k-ary Tree
1. Introduction
Let G and H be finite graphs with n vertices.


VG and

VH denote the vertex sets of G and H, respectively.

EG and

EH denote the edge sets of G and H,
respectively. An embedding f of G into H is defined
[1] as follows:
1) f is a bijective map from


VG VH
2) f is a one-to-one map from


EG to
  


,:
f
Pfufv
  
,
f
Pfufvis a path in H be-
tween

f
uand


f
v.
The dilation of an embedding f of G into H is given by
    

=max,: ,
f
dilfPfufvu vEG
where
  
,
f
Pfufv denotes the length of the path
f
P. Then, the dilation of G into H is defined as




,=mindilGHdilf
where the minimum is taken over all embeddings f of G
into H. Embedding G into H with minimum dilation is
important for network design and for the simulation of
one computer architecture by another [2].
Embeddings as mathematical models of parallel com-
puting have been discussed extensively in the literature
[3,4]. In these models, both the algorithm to be imple-
mented and the interconnection network of the parallel
computing system are represented by graphs. The im-
plementation details are then studied through the embed-
ding.
A tree is a connected graph that contains no cycles.
Trees are the most fundamental graph-theoretic models
used in many fields: information theory, automatics clas-
sification, data structure and analysis, artificial intelli-
gence, design of algorithms, operation research, combi-
natorial optimization, theory of electrical networks and
design of network [5]. Trees are ubiquitous in computer
science. A rooted tree represents a data structure with a
hierarchical relationship among its various elements [6].
The most common type of tree is the binary tree. It is
so named because each node can have at most two des-
cendents. Binary trees are widely used in data structures
because they are easily stored, easily manipulated and
easily retrieved [5]. A k-ary tree is a rooted tree in which
each node has no more than k children. It is also known
as a k-way tree.
From a computing perspective, trees form an impor-
tant class of computational structures. Many operations
such as searching and storing can be easily performed on
tree data structures. Hence, there is a large literature on
embeddings of various kinds of trees into the graphs of
interconnection networks [3,7-25]. In particular, embed-
dings of binary trees into hypercubes have received spe-
cial attention since they naturally arise as the computa-
tional structures of algorithms that employ dvide-and-
conquer paradigm [12].
Hypercubes are very popular models for paralled
computation because of their regularity and the relatively
small number of interprocessor connections. The hyper-
cube embedding problem is the problem of mapping a
communication graph into a hypercube multiprocessor.
Hypercubes are known to be able to simulate other
structures such as grids and binary trees [3,26]. It has
been shown that an arbitrary binary tree can be embed-
*This work is su
pp
or
t
ed b
y
DST Pro
j
ect No. SR/S4/MS: 494/07.

I. RAJASINGH ET AL.
500
ded into a hypercube with constant dilation [26].
In 1984, Havel [9,27] conjectured that a binary tree
can be embedded into a k-dimensional hypercube k Q
with dilation one if and only if each of its partite sets
contains at most 1 2k vertices. In 1985, Bhatt and Ipsen
[7] conjectured that a binary tree can be embedded into
its optimal hypercube with dilation at most two as well
as into its next-to-optimal hypercube with dilation one.
As observed in [13], the conjecture of Havel is stronger
than those of Bhatt and Ipsen. Though all these problems
have been resolved in several special cases, they still
remain open for the general case.
Monien and Sudborough [14] proved that every binary
tree can be embedded into a hypercube with dilation 3
and


1O expansion. Chen and Stallmann [26] proved
that a simple linear-time heuristic embeds an arbitrary
binary tree into a hypercube with expansion 1 and aver-
age dilation no more than 2. Dvořák [15] constructed the
embedding of certain classes of binary trees into hyper-
cubes based on an iterative embedding into their sub-
graphs induced by dense sets. Heun and Mayr [16]
proved that arbitrary binary trees can be embedded into
hypercubes with dialtion 8. Further, they constructed an
embedding of double-rooted complete binary trees into
hypercubes [17]. Sunitha [4] constructed an embedding
of some hierarchical caterpillars into their optimal
hypercube with dilation 2. Choudum et al. [28] proved
that subclasses of height-balanced trees can be embedded
into hypercubes. Further, they proved that the height-balanced
trees and Fibonacci trees can be embedded into hypercubes
[6]. Eğecioğlu and Ibel [18] proved that the dynamic
k-ary tree can be embedded into its asymptotic hyper-
cube.
Thus there is a vast literature on embedding trees into
hypercubes. In this paper, we define an m-sequential
k-ary tree and prove that it can be embedded into its op-
timal hypercube with dilation at most 2.
2. Preliminaries
In this section, we introduce the labeling hal to label the
vertices of the hypercube architecture. We obtain results
that enable us to prove the main result of this paper.
Definition 1 [5] An r-dimensional hypercube r Q has
nodes respesented by all the binary r-tuples with two
nodes being adjacent if and only if their corresponding
r-tuples differ in exactly one position.
The decimal representation of the vertices is the set

0,1, 2,, 21.
nFor convenience, we use the symbol
1x instead of x and therefore the set of labels of the
vertices is

1, 2,, 2.
n

Remark 1 Let G be graph with m vertices. The
hypercube of dimension

2
log m



 is called its optimal
hypercube, and one of dimension

21
log m

is called
next-to-optimal.
Definition 2 Let r Q be an r-dimensional hypercube.
A partial ordering “

” on r
Q is defined by ji QQ 
if and only if i
Q is a subcube of j Q, 1,ij r . The
notation jiQQ < shall mean ji QQ  and .
ij
QQ
Definition 3 A hamiltonian labeling of hypercub e r
Q,
denoted by hal, is the labeling of the vertices of r
Q
defined inductively as follows: Consider the ordering
12
<<<<<
ir
QQQ Q on r
Q. Label vertices of
1
Q as 0 and 1. If ()
i
uVQ is labeled
x
, then label
the unique vertex






1\ ii
vVQ VQ

 adjacent to u
as 1
21
i
x


.
Remark 2 The labeling hal is the decimal equivalent
of the binary gray code sequence [26].
Definition 4 A hamiltonian cycle is a cycle that visits
each node of the graph exactly once. By convention, the
trivial graph on a single node is considered to possess a
hamiltonian cycle. A graph possessing a hamiltonian
cycle is said to be a hamiltonian graph.
Theorem 1 The hamiltonian labeling hal of r
Q
determines a hamiltonian cycle


=1,2, ,2,1
r
r
C in
r
Q，2.r
Proof We prove that hal determines the hamiltonian
cycle


1, 2,, 2,1
l
 in l
Q for all ,l.2 rl  We prove
the result by induction on .r For 2,=r


2=1,2,3,4,1C
is a hamiltonian cycle in 2.QAssume that


1
1=1,2,3,,2 ,1
k
k
C
is a hamiltonian cycle in 1.
k
Q

Consider k
Q. We observe that 1k Qis a subcube of
.
k
Q Let 1k
F
denote the other

1k-dimensional
subcube contained in .
k
QBy definition of k Q,


,uv
is an edge in 1k
Q

if and only if


,
''
uv is an edge in
1k
F
, where


,' uu and


,' vv are edges in .
k
QThus
=P


1
1,2,3, ,2k

 is a hamiltonian path in 1k Q
implying that




1
=2+ 11,2 + 12,,2 + 12
kk kk
P

 



1
=2,21,,2 +1
kk k

is a hamiltonian path in 1k F. Moreover, the vertex
labeled 1
2k is adjacent to the vertex labeled


11
212=2 1
kkk

. Again the vertex labeled 1 is
adjacent to the vertex labeled

211=2.
kk
 Thus





 
1
11 11
2 ,212,1=1,2,,2 ,21,,2,1
kk' kkkk
PP

 

is a hamiltonian cycle in k Q.
The following results are easy consequences of
Theorem 1 and the hal labeling of vertices of the
hypercube.
Lemma 1 Let
x
and y be the hal labeling of
vertices u and v in .
r
QIf m yx 2= for some m,
rm


1, then


,=2duv in .
r
Q
Proof Without loss of generality let y
x
>. Now

11
=2=22= 2121
mmmm m
x
yxyz z


 ,

I. RAJASINGH ET AL.
501
where z is the label of some vertex w in .
r
QThus

1
=21,=21
mm
x
zy z
 is a solution to the
equation =2 .
m
xy This implies that w is adjacent to
both u and v. In other words,

,=2duv in .
r
Q
Lemma 2 Let x and y be the hal labeling of vertices u
and v in .
r
QIf 122=  xxy m for some m,
1,mr then 1=),( vud in .
r
Q
Lemma 3 Let 1 and y be the hal labeling of vertices u
and v in .
r
QIf mim y22=1   for some m and i,
1,m,ir then 2=),( vud in .
r
Q
Proof It is straightforward to see that mim
y22=1 
implies 12= 
zy im , where m
z2= is the label of
some vertex w in .
r
QThus, {=21 ,=2}
mi m
yzz
 is a
solution to the equation 1=22 .
mi m
y 
This implies
that w is adjacent to both u and v. In other words,
2=),( vud in .
r
Q
3. Embedding Algorithm
Embeddings with dilation more than one become
significant when trees with branch lengths representing
time are considered. In this section, we obtain an
embedding algorithm and prove its correctness.
Definition 5 A rooted tree T is said to be a step-up
tree if for every internal node u of T, any two subtrees
i
T and j T rooted at children of u are ordered in T in
such a way that if



ij
VT VT, then i T lies to the
left of j T. See Figure 1.
Definition 6 For 2m and 1k, an m-sequential
k-ary tree T(m,k) is a step-up tree obtained by
recursively growing the root u with k children under the
following conditions.
(a) The subtrees rooted at the children of u are of
sequential order


12 2
22,2 ,2,2,,2
mmmmmk 
 or

12 1
21,2,2, ,2.
mmm mk 

(b) The root of a subtree of order t
s2, 20


t,
3s has 1s children which in turn are the roots of
subtrees of sequential order

232 1
3,2 ,2 ,,2,2
sst 


except when =3, =2st
and in this case the sequential
order is (2, 3).
(c) A subtree of order 3 or 4 with v as a root node is
isomorphic to one of the graphs shown in Fi gure 2.
T
1
T
2 T
3
T
k
u
Figure 1. Step-up tree T with





12
VTVT


k VT .
v
vv
vvv
Figure 2. A subtree of order 3 or 4 with v as a root node.
Remark 3 ),(kmT rooted at u is said to be of Type
A or Type B depending whether the subtrees rooted at the
children of u are of sequential order 1 (22,2 ,2,
mmm


22
2,,2 )
mmk
 or


12 1
21,2,2, ,2,
mmm mk 
res-
pectively. See Figure 3.
Remark 4 ),( kmT of Type A has 12 3

km nodes
and ),( kmT of Type B has

22 1
mk
 nodes.
In the sequel, we need the following definition of
pre-order tree traversal.
Definition 7 Let T be a rooted tree. A pre-order
labeling of nodes of T is the lab eling of its nodes the first
time we visit the nodes in the traversal. See Figure 4.
Embedding Algorithm
Input: ),(kmT and its optimal hypercube .
r
Q
Algorithm: Label the nodes of T using pre-order
labeling and the vertices of the hypercube using hal
labeling.
Output: Embedding of T into r
Q with dilation at
most 2. See Figure 5.
(a) (b)
Figure 3. (a) T (2, 4) of Type A; (b) T (3, 2) of Type B.
1
2
3
4
56
7
8
9
10 11
12
13 14
15
Figure 4. A pre-order labeling of nodes of T.

I. RAJASINGH ET AL. 502
1
2
3
4
56
7
8
9
10 11
12
13 14
15
hal
1
5
4
2
7
3
6
16 15
14 13
1089
11 12
Figure 5. Embedding of T(2, 3) of Type A into Q4.
Theorem 2 An m-sequential k-ary tree can be embedded
into its optimal hypercube with dilation at most 2.
Proof Consider an embedding f of T into r Q using
the embedding algorithm, labeling the nodes of T using
pre-order labeling and the vertices of the hypercube
using hal labeling such that xxf =)(.
Let v be an internal node of T with children
12
,, ,
p
vv v. Let 12
,, ,
p
TT T be the subtrees rooted at
12
,,,,
p
vv v respectively. Since T is a step-up tree, we
have
  

12 . p
VT VTVT Suppose that the root of
T is u. Then the label of u is 1.
Case 1 (v is a child of u):
Let )(1,= ii ye , 1.ik
By definition of pre-order traversal,






12 1
=2.
ii
yVTVTVT

 
By definition of m-sequential k-ary tree of Type A,
  

12 1
12 (3)
34
=22 2222
=2 [122]2=22.
i
mmmm mi
mimi
VT VTVT

 


 
 



Therefore 12=1 4 im
i
y and hence by Lemma 2,
the edge i
e is of dilation 1.
Again by definition of m-sequential k-ary tree of Type B,







12 1
12 (1)
1
=21 222
=21221=221.
i
mmm mi
mimii
VT VTVT

 


 
 



Therefore iim
i
y22=1   and hence by Lemma 3, the
edge i e is of dilation 2.
Case 2 (v is not a child of u):
Let the label of v be x. Let ),(= ii yxe , 1.ip
By definition of pre-order traversal,






12 1
=1.
ii
yVT VTVTx

 
By definition of m-sequential k-ary tree,






1
12 1
=3 42=2 1.
ii
i
VT VTVT


 
Therefore i
ixy 2= and hence by Lemma 1, the edge
i
e is of dilation 2.
4. Conclusions
In this paper, we have obtained an embedding algorithm
to embed an m-sequential k-ary tree into its optimal
hypercube with dilation at most 2. We have also proved
its correctness. This study is important as the embedding
of binary trees into hypercubes received special attention
in the computational structures of algorithm such as
searching and storing.
5. References
[1] S. L. Bezrukov, J. D. Chavez, L. H. Harper, M. Röttger
and U. P. Schroeder, “Embedding of Hypercubes into
Grids,” Proceedings of the 23rd International Symposium
on Mathematical Foundations of Computer Science, Brno,
24-28 August 1998 , pp. 693-701.
[2] S. L. Bezrukov, B. Monien, W. Unger and G. Wechsung,
“Embedding Ladders and Caterpillars into the Hyper-
cube,” Discrete Applied Mathematics, Vol. 83, No. 1-3,
1998, pp. 21-29.
[3] P. Manuel, I. Rajasingh, B. Rajan and H. Mercy, “Exact
Wirelength of Hypercube on a Grid,” Discrete Applied
Mathematics, Vol. 157, No. 7, 2009, pp. 1486-1495.
[4] V. Sunitha, “Embedding Some Hierarchical Caterpillars
into Hypercube,” Electronic Notes in Discrete Mathe-
matics, Vol. 22, No. 10, 2005, pp. 387-389.
[5] J. M. Xu, “Topological Structure and Analysis of Inter-
connection Networks,” Kluwer Academic Publishers,
Norwell, 2001.
[6] S. A. Choudum and I. Raman, “Embedding Height Ba-
lanced Trees and Fibonacci Trees in Hypercubes,” Journal of
Applied Mathematics and Computing, Vol. 30, No. 1-2,

I. RAJASINGH ET AL.
503
2009, pp. 39-52.
[7] S. N. Bhatt and I. C. Ipsen, “How to Embed Trees in
Hypercubes,” Technical Report YALEU/DCS/RR-443,
Yale University, Connecticut, 1985.
[8] Q. Dong, X. Yang, J. Zhao and Y. Y. Tang,“Embbedding a
Family of Disjoint 3D Meshes into a Crossed Cube,” Infor-
mation Sciences, Vol. 178, No. 11, 2008, pp. 2396-2405.
[9] I. Havel, “On Hamiltonian Circuits and Spanning Trees
of Hypercubes,” Casopis.Pest.Mat., Vol. 109, No. 2,
1984, pp. 135- 152.
[10] I. Havel and P. Liebl, “O Vnoren Dichotomickeho Stro-
mu Do Krychle (in Czech with English summary),”
Casopis. Pest. Mat., Vol. 97 , No. 2, 1972, pp. 201-205.
[11] L. Nebesky, “On Cubes and Dichotomic Trees,” Casopis.
Pest. Mat., Vol. 99, No. 2, 1974, pp. 164-167.
[12] D. E. Knuth, “The Art of Computer Programming-3,
Sorting and Searching,” Addison-Wesley Publishing
Company, Massachusetts, 1973.
[13] T. Dvořák, I. Havel, P. Liebl and J.-M. Laborde, “Gene-
ralized Hypercubes and Graph Embedding with Dila-
tion,” Rostocker Mathematisches Kolloquium, Vol. 39,
1990, pp. 13-20.
[14] B. Monien and H. Sudborough, “Simulating Binary Trees
on Hypercubes,”VLSI, Algorithms and Architectures,
Proceedings of the 3rd Aegean Workshop on Computing,
LNCS, Springer-Verlag Vol. 319, No. 24, 1988, pp.
170-180.
[15] T. Dvořák, “Dense Sets and Embedding Binary Trees
into Hypercubes,”Discrete Applied Mathematics, Vol.
155, No. 4, 2007, pp. 506-514.
[16] V. Heun and E. W. Mayr, “A New Efficient Algorithm
for Embedding an Arbitrary Binary Tree into Its Optimal
Hypercube,”Journal of Algorithms, Vol. 20, No. 2, 1996,
pp. 375-399.
[17] V. Heun and E. W. Mayr, “Optimal Dynamic Em-
beddings of Complete Binary Trees into Hypercubes,”
Journal of Parallel and Distributed Computing, Vol. 61,
No. 8, 2001, pp. 1110-1125.
[18] O. Eğecioğlu and M. Ibel, “Asymptotic Hypercube Em-
beddings of Dynamic k-ary Trees,” Congressus Nume-
rantium, Vol. 126, 1997, pp. 21-32.
[19] J. Fan and X. Jia, “Embedding Meshes into Crossed
Cubes,” Information Sciences, Vol. 177, No. 15, 2007,
pp. 3151-3160.
[20] J. Fan, X. Jia and X. Lin,“Complete Path Embeddings in
Crossed Cubes,” Information Sciences, Vol. 176, No. 22,
2006, pp. 3332-3346.
[21] J. S. Fu, “Longest Fault-free Paths in Hypercubes with
Vertex Faults,” Information Sciences, Vol. 176, No. 7,
2006, pp. 759-771.
[22] I. Havel and P. Liebl,“One-Legged Caterpillars Span
Hypercubes,”Journal of Graph Theory, Vol. 10, No. 1,
1986, pp. 69-77.
[23] T. C. Lin and D. R. Duh, “Constructing Vertex-Disjoint
Paths in (n, k)-star Graphs,”Information Sciences, Vol.
178, No. 3, 2008, pp. 788-801.
[24] C. H. Tsai and Y. C. Lai, “Conditional Edge-Fault-Tolerant
Edge-Bipancyclicity of Hypercubes,” Information Sciences,
Vol. 177, No. 24, 2007, pp. 5590-5597.
[25] R. Y. Wu, G. Chen, Y-L. Kuo and G. J. Chang, “Node-
disjoint Paths in Hierarchical Hypercube Networks,”
Information Sciences, Vol. 177, No. 19, 2007, pp.
4200-4207.
[26] W. K. Chen and M. F. M. Stallmann,“On Embedding
Binary Trees into Hypercubes,” Journal on Parallel and
Distributed Computing, Vol. 24, No. 2, 1995, pp. 132-138.
[27] I. Havel, “On Certain Trees in Hypercubes,” In Topics in
Combinatorics and Graph Theory, Physica-Verlag,
Heidelberg, 1990, pp. 353-358.
[28] S. A. Choudum and I. Raman, “On Embedding
Subclasses of Height-balanced Trees in Hypercubes,”
Journal of Applied Mathematics, Vol. 179, No. 9, 2009, pp.
1333-1347.