Abstract

Graph embedding is the mapping of a topological structure (guest graph) into another topological structure (host graph) that preserves certain required topological properties and the graph embedding ability reflects how efficiently a parallel algorithm with a guest graph can be executed on a host graph [#!Pa99!#] and the utilization of system resources in the host graph [#!KiBh08!#]. In this paper, we obtain exact wirelength of embedding complete multipartite graphs into cycle-of-ladders.

Citation details of the article

Journal: International Journal of Applied Mathematics
Journal ISSN (Print): ISSN 1311-1728
Journal ISSN (Electronic): ISSN 1314-8060
Volume: 32
Issue: 6
Year: 2019

DOI: 10.12732/ijam.v32i6.3

Download Section

Download the full text of article from here.

You will need Adobe Acrobat reader. For more information and free download of the reader, please follow this link.

References

1. [1] B. Parhami, An Introduction to Parallel Processing: Algorithms and Architectures, Plenum Press, New York, 1999.
2. [2] V. Kianzad, S.S. Bhattacharyya, Efficient techniques for clustering and scheduling onto embedded multiprocessors, IEEE Transactions on Parallel and Distributed Systems, 17, No 7 (2006), 1847-1849.
3. [3] H.S. Lim, J.H. Park, K.Y. Chwa, Embedding trees in recursive circulants, Discrete Applied Mathcmatlcs, 69 (1996), 83-99.
4. [4] J. Opatrny, D. Sotteau, Embeddings of complete binary trees into grids and extended grids with total vertex-congestion, Discrete Applied Mathematics, 98 (2000), 237-254.
5. [5] S.L. Bezrukov, J.D. Chavez, L.H. Harper, M. Röttger, U.P. Schroeder, The congestion of n-cube layout on a rectangular grid, Discrete Mathematics, 213 (2000), 13-19.
6. [6] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan, New York, 1976.
7. [7] J.-B. Liu, S. Wang, C. Wang, S. Hayat, Further results on computation of topological indices of certain networks, IET Control Theory Appl.; DOI: 10.1049/ietcta.2016.1237.
8. [8] S. Wang, B. Wei, Multiplicative Zagreb indices of k-trees, Discrete Appl. Math., 180 (2015), 168-175.
9. [9] J.-B. Liu, C. Wang, S. Wang, B. Wei, Zagreb indices and multiplicative Zagreb indices of eulerian graphs, Bull. Malays. Math. Sci. Soc.; DOI: 10.1007/s40840-017-0463-2.
10. [10] J.M. Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic Publishers, 2001.
11. [11] Y.L. Lai, K. Williams, A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs, J. Graph Theory, 31 (1999), 75-94.
12. [12] I. Rajasingh, J. Quadras, P. Manuel, A. William, Embedding of cycles and wheels into arbitrary trees, Networks, 44 (2004), 173-178.
13. [13] A.K. Gupta, D. Nelson, H. Wang, Efficient embeddings of ternary trees into hypercubes, J. of Parallel and Distributed Computing, 63, No 6 (2003), 619-629.
14. [14] J. Fan, X. Jia, Embedding meshes into crossed cubes, Information Sciences, 177, No 15 (2007), 3151-3160.
15. [15] W.K. Chen, M.F.M. Stallmann, On embedding binary trees into hypercubes, Information Sciences, 24 (1995), 132-138.
16. [16] S.L. Bezrukov, Embedding complete trees into the hypercube, Discrete Applied Mathematics, 110, No 2-3 (2001), 101-119.
17. [17] J.F. Fang, K.C. Lai, Embedding the incomplete hypercube in books, Information Processing Letters, 96 (2005), 1-6.
18. [18] P.L. Lai, C.H. Tsai, Embedding of tori and grids into twisted cubes, Theoretical Computer Science, 411, No 40-42 (2010), 3763-3773.
19. [19] Y. Han, J. Fan, S. Zhang, J. Yang, P. Qian, Embedding meshes into locally twisted cubes, Information Sciences, 180, No 19 (2010), 3794-3805.
20. [20] R. Caha, V. Koubek, Optimal embeddings of generalized ladders into hypercubes, Discrete Mathematics, 233 (2001), 65-83.
21. [21] M. Rottger, U.P. Schroeder, Efficient embeddings of grids into grids, Discrete Applied Mathematics, 108, No 1-2 (2001), 143-173.
22. [22] J.D. Chavez, R. Trapp, The cyclic cutwidth of trees, Discrete Applied Mathematics, 87 (1998), 25-328.
23. [23] C.J. Guu, The Circular Wirelength Problem for Hypercubes, Ph.D. Dissertation, University of California, Riverside, 1997.
24. [24] M.C. Yang, Path embedding in star graphs, Applied Mathematics and Computation, 207, No 2 (2009), 283-291.
25. [25] C.H. Tsai, Embedding of meshes in M oobius cubes, Theoretical Computer Science, 401, No 1-3 (2008), 181-190.
26. [26] P. Manuel, Minimum average congestion of enhanced and augmented hypercube into complete binary tree, Discrete Applied Mathematics, 159, No 5 (2010), 360-366.
27. [27] M.R Garey, D.S Johnson DS, Computers and Intractability, a Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.
28. [28] I. Rajasingh, P. Manuel, M. Arockiaraj B. Rajan, Embeddings of circulant networks, Journal of Combinatorial Optimization, 26, No 1 (2013), 135151.
29. [29] P. Manuel, M. Arockiaraj, I. Rajasingh, B. Rajan, Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength, Discrete Applied Mathematics, 159, No 17 (2011), 2109-2116.
30. [30] I. Rajasingh, B. Rajan, R.S. Rajan, Embedding of special classes of circulant networks, hypercubes and generalized Petersen graphs, International Journal of Computer Mathematics, 89, No 1 (2012), 1970-1978.
31. [31] S.L. Bezrukov, S.K. Das, R. Elsässer, An edge-isoperimetric problem for powers of the Petersen graph, Annals of Combinatorics, 4 (2000), 153-169.
32. [32] P. Manuel, I.Rajasingh, B.Rajan, H. Mercy, Exact wirelength of hypercube on a grid, Discrete Appl. Math., 157, No 7 (2009), 1486-1495.
33. [33] J.F. Fang, The bipancycle-connectivity of the hypercube, Information Sciences, 178 (2008), 4679-4687.
34. [34] S.K. Vaidya, S. Srivastav, V.J. Kaneria, G.V. Ghodasara, Cordial and 3-equitable labeling of star of a cycle, Discrete Mathematics, 24 (2008), 54-64.
35. [35] R.S. Rajan, T.M Rajalaxmi, Jia-Baco, G. Sethuraman, Wirelength of embedding complete multipartite graphs into certain graphs, Manuscript.
36. [36] M. Miller, R.S. Rajan, N. Parthiban, I. Rajasingh, Minimimum linear arrangment of incomlete hypercubes, The Computer Journal, No 2 (2015), 331-337.