 Applied Mathematics, 2010, 3, 499-503 doi:10.4236/am.2010.16065 Published Online December 2010 (http://www.SciRP.org/journal/am) Copyright © 2010 SciRes. 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 E-mail: hellosundar@rediffmail.com 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  as follows: 1) f is a bijective map from VG VH 2) f is a one-to-one map from EG to  ,:fPfufv  ,fPfufvis a path in H be-tweenfuandfv. The dilation of an embedding f of G into H is given by   =max,: ,fdilfPfufvu vEG where  ,fPfufv denotes the length of the path fP. 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 . 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 . Trees are ubiquitous in computer science. A rooted tree represents a data structure with a hierarchical relationship among its various elements . 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 . 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 . 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 supported by DST Project No. SR/S4/MS: 494/07. I. RAJASINGH ET AL. Copyright © 2010 SciRes. AM 500 ded into a hypercube with constant dilation . In 1984, Havel [9,27] conjectured that a binary tree can be embedded into a k-dimensional hypercube kQ with dilation one if and only if each of its partite sets contains at most 12k vertices. In 1985, Bhatt and Ipsen  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 , 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  proved that every binary tree can be embedded into a hypercube with dilation 3 and 1O expansion. Chen and Stallmann  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  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  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 . Sunitha  constructed an embedding of some hierarchical caterpillars into their optimal hypercube with dilation 2. Choudum et al.  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 . Eğecioğlu and Ibel  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  An r-dimensional hypercube rQ 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 2log m is called its optimal hypercube, and one of dimension 21log m is called next-to-optimal. Definition 2 Let rQ be an r-dimensional hypercube. A partial ordering “” on rQ is defined by ji QQ  if and only if iQ is a subcube of jQ, 1,ij r. The notation jiQQ < shall mean ji QQ  and .ijQQ Definition 3 A hamiltonian labeling of hypercub e rQ, denoted by hal, is the labeling of the vertices of rQ defined inductively as follows: Consider the ordering 12<<<<. Now 11=2=22= 2121mmmm mxyxyz z , I. RAJASINGH ET AL. Copyright © 2010 SciRes. AM 501where z is the label of some vertex w in .rQThus 1=21,=21mmxzy z is a solution to the equation =2 .mxy This implies that w is adjacent to both u and v. In other words, ,=2duv in .rQ Lemma 2 Let x and y be the hal labeling of vertices u and v in .rQIf 122=  xxy m for some m, 1,mr then 1=),( vud in .rQ Lemma 3 Let 1 and y be the hal labeling of vertices u and v in .rQIf mimy22=1   for some m and i, 1,m,ir then 2=),( vud in .rQ Proof It is straightforward to see that mimy22=1  implies 12= zy im , where mz2= is the label of some vertex w in .rQThus, {=21 ,=2}mi myzz is a solution to the equation 1=22 .mi myThis implies that w is adjacent to both u and v. In other words, 2=),( vud in .rQ 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 iT and jT rooted at children of u are ordered in T in such a way that if ijVT VT, then iT lies to the left of jT. 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 222,2 ,2,2,,2mmmmmk  or 12 121,2,2, ,2.mmm mk  (b) The root of a subtree of order ts2, 20t, 3s has 1s children which in turn are the roots of subtrees of sequential order 232 13,2 ,2 ,,2,2sst 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. T1T2T3Tku Figure 1. Step-up tree T with  12VTVT  kVT . vvvvvv 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 222,,2 )mmk or 12 121,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 1mk 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 .rQ Algorithm: Label the nodes of T using pre-order labeling and the vertices of the hypercube using hal labeling. Output: Embedding of T into rQ 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. 12345678910 111213 1415 Figure 4. A pre-order labeling of nodes of T. I. RAJASINGH ET AL. Copyright © 2010 SciRes. AM 502 12345678910 111213 1415hal154273616 15141310891112 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 rQ 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,, ,pvv v. Let 12,, ,pTT T be the subtrees rooted at 12,,,,pvv v respectively. Since T is a step-up tree, we have  12 .pVT 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.iiyVTVTVT  By definition of m-sequential k-ary tree of Type A,  12 112 (3)34=22 2222=2 2=22.immmm mimimiVT VTVT    Therefore 12=1 4 imiy and hence by Lemma 2, the edge ie is of dilation 1. Again by definition of m-sequential k-ary tree of Type B, 12 112 (1)1=21 222=21221=221.immm mimimiiVT VTVT    Therefore iimiy22=1   and hence by Lemma 3, the edge ie 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.iiyVT VTVTx  By definition of m-sequential k-ary tree, 112 1=3 42=2 1.iiiVT VTVT  Therefore iixy 2= and hence by Lemma 1, the edge ie 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  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.  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.  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.  V. Sunitha, “Embedding Some Hierarchical Caterpillars into Hypercube,” Electronic Notes in Discrete Mathe- matics, Vol. 22, No. 10, 2005, pp. 387-389.  J. M. Xu, “Topological Structure and Analysis of Inter- connection Networks,” Kluwer Academic Publishers, Norwell, 2001.  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. Copyright © 2010 SciRes. AM 5032009, pp. 39-52.  S. N. Bhatt and I. C. Ipsen, “How to Embed Trees in Hypercubes,” Technical Report YALEU/DCS/RR-443, Yale University, Connecticut, 1985.  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.  I. Havel, “On Hamiltonian Circuits and Spanning Trees of Hypercubes,” Casopis.Pest.Mat., Vol. 109, No. 2, 1984, pp. 135- 152.  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.  L. Nebesky, “On Cubes and Dichotomic Trees,” Casopis. Pest. Mat., Vol. 99, No. 2, 1974, pp. 164-167.  D. E. Knuth, “The Art of Computer Programming-3, Sorting and Searching,” Addison-Wesley Publishing Company, Massachusetts, 1973.  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.  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.  T. Dvořák, “Dense Sets and Embedding Binary Trees into Hypercubes,”Discrete Applied Mathematics, Vol. 155, No. 4, 2007, pp. 506-514.  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.  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.  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.  J. Fan and X. Jia, “Embedding Meshes into Crossed Cubes,” Information Sciences, Vol. 177, No. 15, 2007, pp. 3151-3160.  J. Fan, X. Jia and X. Lin,“Complete Path Embeddings in Crossed Cubes,” Information Sciences, Vol. 176, No. 22, 2006, pp. 3332-3346.  J. S. Fu, “Longest Fault-free Paths in Hypercubes with Vertex Faults,” Information Sciences, Vol. 176, No. 7, 2006, pp. 759-771.  I. Havel and P. Liebl,“One-Legged Caterpillars Span Hypercubes,”Journal of Graph Theory, Vol. 10, No. 1, 1986, pp. 69-77.  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.  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.  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.  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.  I. Havel, “On Certain Trees in Hypercubes,” In Topics in Combinatorics and Graph Theory, Physica-Verlag, Heidelberg, 1990, pp. 353-358.  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.