Loading...
Embedding Wheel-like Networks
Rajan, R. Sundara Rajalaxmi, Rajalaksmi Stephen, Sudeep Shantrinal, A. Arul Kumar, K. Jagadeesh
Rajan, R. Sundara
Rajalaxmi, Rajalaksmi
Stephen, Sudeep
Shantrinal, A. Arul
Kumar, K. Jagadeesh
Abstract
One of the important features of an interconnection network is its ability to efficiently simulate programs or parallel algorithms written for other architectures. Such a simulation problem can be mathematically formulated as a graph embedding problem. In this paper we compute the lower bound for dilation and congestion of embedding onto wheel-like networks. Further, we compute the exact dilation of embedding wheellike networks into hypertrees, proving that the lower bound obtained is sharp. Again, we compute the exact congestion of embedding windmill graphs into circulant graphs, proving that the lower bound obtained is sharp. Further, we compute the exact wirelength of embedding wheels and fans into 1,2-fault hamiltonian graphs. Using this we estimate the exact wirelength of embedding wheels and fans into circulant graphs, generalized Petersen graphs, augmented cubes, crossed cubes, Möbius cubes, twisted cubes, twisted n-cubes, locally twisted cubes, generalized twisted cubes, odd-dimensional cube connected cycle, hierarchical cubic networks, alternating group graphs, arrangement graphs, 3-regular planer hamiltonian graphs, star graphs, generalised matching networks, fully connected cubic networks, tori and 1-fault traceable graphs.
Keywords
Embedding, Wheel, Friendship graph, Median, Hamiltonian
Date
2023
Type
Journal article
Journal
Book
Volume
18
Issue
2
Page Range
185-198
Article Number
ACU Department
School of Arts and Humanities
Faculty of Education and Arts
Faculty of Education and Arts
Collections
Relation URI
Source URL
Event URL
Open Access Status
Open access
License
CC BY-NC 4.0
File Access
Open
Notes
©2023 Academic Center for Education, Culture and Research TMU
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.