Abstract

We present an approach to find the edge congestion sum and dilation sum forembedding of square of cycle on n vertices, Cn2, and Cn2?1 + K1 into arbitrary tree. The embedding algorithms use a technique based on consecutive label property. Our algorithm calculates edge congestion in linear time.

References

• N. Bagherzadeh, M. Dowds, and N. Nassif, Embedding an arbitrary tree into the star graph, IEEE Transactions on Computers 45 (1996).
• D. Barth, P. Fragopoulou, and M. C. Heydemann, Uniform emulations of Cartesian-product and Cayley graphs, Discrete Appl Math 116 (2002).
• S. Bettayeb, B. Cong, M. Girou, and I. H. Sudborough,Embedding of star networks into hypercubes, IEEE Transact Comput 45 (1996).
• S. L. Bezrukov, Embedding complete trees into the hypercube, Discrete Appl Math 110 (2001).
• S. L. Bezrukov, J. D. Chavez, L. H. Harper, M. Ro¨ttger, and U. P. Schroeder, Embedding of hypercubes into grids, MFCS, 1998, 693–701, (Electronic Edition, Springer, Lecture Notes in Computer Science 1450).
• S. L. Bezrukov, J. D. Chavez, L. H. Harper, M. Ro¨ttger, and U. P. Schroeder, The congestion of n-cube layout on a rectangular grid, Discrete Math 213 (2000).
• S. Bezrukov, B. Monien, W. Unger, and G. Wechsung, Embedding ladders and caterpillars into the hypercube, Discrete Appl Math 83 (1998).
• D. Bienstock, On embedding graphs in trees, J Combin Theory Ser B 49 (1990).
• A. Bouabdallah, M. C. Heydemann, J. Opatrny, and D. Sotteau, Embedding complete binary trees into star and pancake graphs, Theory ComputSyst 31 (1998).
• R. Caha and V. Koubek, Optimal embeddings of generalized ladders into hypercubes, Discrete Math 233 (2001).
• J. D. Chavez and R. Trapp, The cyclic cutwidth of trees,DiscreteAppl Math 87 (1998).
• M. Chrobak and W. Rytter, Two results on linear embeddings of complete binary trees, TheoretComputSci 136(1994).
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,Introduction to algorithms, MIT Press and McGraw-Hill,New York, 2001.
• J. Diaz, J. Petit, and M. Serna, A survey of graph layout problems, Comput Surveys 34 (2002).
• D. Eichhorn, D. Mubayi, K. O'Bryant, and D. B. West, The edge-bandwidth of theta graphs, J Graph Theory 35 (2000).
• M. C. Golumbic, Algorithmic graph theory and perfect graphs, Academic Press, New York, 1980.
• F. Harary, Graph theory, Narosa Publishing House, New Delhi, 2001.
• L. T. Q. Hung, M. M. Syslo, M. L. Weaver, and D. B. West, Bandwidth and density for block graphs, Discrete Math 189 (1998).
• M. Klugerman, A. Russell, and R. Sundaram, On Embedding complete graphs into hypercubes, Discrete Math 186(1998).
• Y. L. Lai and K. Williams, A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs, J Graph Theory 31 (1999).
• T. F. Leighton, Introduction to parallel algorithms and architecture: Arrays, trees, hypercubes, Morgan Kaufmann Publishers, San Mateo, CA, 1992.
• A. Matsubayashi and S. Ueno, Small congestion Embedding of graphs into hypercubes, Networks 33 (1999).
• J. Opatrny and D. Sotteau, Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1, Discrete Appl Math 98 (2000).
• J. Quadras, Embeddings and interconnection networks, Ph. D. Thesis, Department of Mathematics, Loyola College, India.
• M. Rottger and U. P. Schroeder, Efficient embeddings of grids into grids, Discrete Appl Math 108 (2001).
• H. Schro¨der, O. Sykora, and I. Vrto, Cyclic cutwidth of the mesh, SOF-SEM'99: Theory and practice of informatics (Milovy), 443–452, Lecture Notes in Computer Science 1725, Springer, Berlin, 1999.
• S. Simonson and I. H. Sudborough, On the complexity of tree embedding problems, Informat Process Lett 44 (1992).
• Y. C. Tseng, Y. S. Chen, T. Y. Juang, and C. J. Chang, Congestion-free, dilation-2 embedding of complete binary trees into star graphs, Networks 33 (1999).
• I. Vrto, Cutwidth of the r-dimensional mesh of d-ary trees, Theor Inform Appl 34 (2000), 515–519.
• Indra Rajasingh and Albert William, JasinthaQuadras and Paul Manuel, Embedding of Cycles and Wheels into Arbitrary Trees, NetworksVol. 44(3),2004
• Indra Rajasingh, BharatiRajan, RamanathanSundaraRajan, On Embedding of m-Sequential k-ary Trees into Hypercubes*,Applied Mathematics, 2010, 3.