Embedding Wheel - like Networks
From MaRDI portal
Publication:6187747
DOI10.61186/IJMSI.18.2.185arXiv1902.03391OpenAlexW4388162832MaRDI QIDQ6187747FDOQ6187747
Authors: R. Sundara Rajan, T. M. Rajalaxmi, Sudeep Stephen, A. Arul Shantrinal, K. Jagadeesh Kumar 
Publication date: 15 January 2024
Published in: Iranian Journal of Mathematical Sciences and Informatics (Search for Journal in Brave)
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 wheel-like 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"{o}bius cubes, twisted cubes, twisted -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.
Full work available at URL: https://arxiv.org/abs/1902.03391
Recommendations
- Exact wirelength of embedding circulant networks into necklace and windmill graphs.
- Exact wirelength of circulant networks into cycle-of-ladders.
- Embedding of cycles and wheels into arbitrary trees
- Embedding circulant networks into butterfly and benes networks
- Embedding of hypercubes into necklace, windmill and snake graphs
Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Eulerian and Hamiltonian graphs (05C45)
Cites Work
- Title not available (Why is that?)
- Survey on path and cycle embedding in some networks
- Arrangement graphs: A class of generalized star graphs
- Locally twisted cubes are 4-pancyclic.
- The Mobius cubes
- Embedding of cycles in twisted cubes with edge-pancyclic
- Embedding meshes into locally twisted cubes
- On some super fault-tolerant Hamiltonian graphs
- Optimal 1-Hamiltonian graphs
- Fault Hamiltonicity and fault Hamiltonian connectivity of the (n,k)-star graphs
- Exact wirelength of hypercubes on a grid
- Wirelength of hypercubes into certain trees
- Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1
- The congestion of \(n\)-cube layout on a rectangular grid
- A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
- Title not available (Why is that?)
- Embedding of cycles and wheels into arbitrary trees
- The cyclic cutwidth of trees
- Efficient embeddings of grids into grids
- Optimal embeddings of generalized ladders into hypercubes
- Embedding of tori and grids into twisted cubes
- Embedding meshes/tori in faulty crossed cubes
- Paths and cycles embedding on faulty enhanced hypercube networks
- Panconnectivity, fault-tolerant hamiltonicity and hamiltonian-connectivity in alternating group graphs
- Augmented cubes
- Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength
- Embedding meshes into crossed cubes
- Wirelength of \(1\)-fault Hamiltonian graphs into wheels and fans
- Embedding of hypercubes into necklace, windmill and snake graphs
- Minimum wirelength of hypercubes into \(n\)-dimensional grid networks
- Embedding of special classes of circulant networks, hypercubes and generalized Petersen graphs
- Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements
- Embedding of meshes in Möbius cubes
- On embedding rectangular grids in hypercubes
- Cycles embedding in folded hypercubes with conditionally faulty vertices
- Two construction schemes for cubic Hamiltonian 1-node-Hamiltonian graphs
- Hyper-Hamiltonian generalized Petersen graphs
- Asymptotics of the average number of nondominant options of binary relations
- Fault Hamiltonicity and fault Hamiltonian-connectivity of generalised matching networks
- Wirelength of embedding complete multipartite graphs into certain graphs
This page was built for publication: Embedding Wheel - like Networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187747)
