Optimization of layout for embedding complete k-partite graphs into line graphs of certain tree architectures
Abstract
The capability of one architecture to simulate another serves as the foundation for network comparison, with embedding playing a key role in analyzing these simulations. In architectural simulation, graph embedding is one of the most powerful techniques for executing parallel algorithms and modeling diverse interconnection networks. In our earlier work, we listed an open problem that the determination of wirelength for embeddings of complete multipartite graphs into line graphs of tree-based interconnection architectures, specifically k-ary trees, banana trees, and firecracker trees. In the present paper, we explicitly construct embeddings of complete k-partite graphs into the line graphs of these three architectures and derive exact wirelength expressions. Thus, this work partially resolves the open problem posed in [1]. These results contribute toward optimized VLSI layout design and efficient Network-on-Chip (NoC) architectures.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2026.14.1.12
References
N. Jothilakshmi, R. S. Rajan, I. Rajasingh, and D. A. Emilet, "Embedding of complete bipartite graphs into some special classes of chordal graph," Journal of Discrete Mathematical Sciences and Cryptography, accepted.
A. A. Shantrinal, S. Klazzar, R. S. Rajan, and T. M. Rajalaxmi, "An algorithm for embedding Turán graphs into incomplete hypercubes with minimum wirelength," Journal of Graph Algorithms and Applications, vol. 25, pp. 367–381, 2021.
R. S. Rajan, T. M. Rajalaxmi, J. B. Liu, and G. Sethuraman, "Wirelength of embedding complete multipartite graphs into certain graphs," Discrete Applied Mathematics, vol. 280, pp. 221–236, 2020.
A. B. Greeni and I. Rajasingh, "Embedding complete bipartite graph into grid with optimum congestion and wirelength," International Journal of Networking and Virtual Organisations, vol. 17, pp. 64–75, 2017.
R. M. Reji and R. S. Rajan, "Optimizing wirelength in embedding Turán graphs into complete binary trees," Springer Proceedings in Mathematics and Statistics, vol. 480, pp. 3–10, 2025.
N. Obata, "Complete multipartite graphs of non-QE class," Electronic Journal of Graph Theory and Applications, vol. 11, pp. 511–527, 2023. doi:10.5614/ejgta.2023.11.2.14
M. M. Legese, "Steiner Wiener index of complete m-ary trees," Iranian Journal of Mathematical Chemistry, vol. 12, pp. 101–109, 2021.
J. Xu, Topological structures and analysis of interconnection networks, Kluwer Academic Publishers, Dordrecht, 2001.
V. E. Levit and D. Tankus, "Generating subgraphs in chordal graphs," Discrete Applied Mathematics, vol. 368, pp. 184–189, 2025.
D. Barth, D. Watel, and M. A. Weisser, "Correcting a graph into a linegraph minimizing Hamming distance edition is NP-complete and FPT by treewidth," Journal of Graph Algorithms and Applications, vol. 28, pp. 63–90, 2024.
S. Afya and M. Rajesh, "MinLA of (K₉ - C₉)ⁿ and its optimal layout into certain trees," The Journal of Supercomputing, vol. 79, pp. 12000–12012, 2023.
R. S. Rajan, A. A. Shantrinal, T. M. Rajalaxmi, J. Fan, and W. Fan, "Embedding complete multi-partite graphs into Cartesian product of paths and cycles," Electronic Journal of Graph Theory and Applications, vol. 9, pp. 507–525, 2021.
J. Quadras and S. S. Surya, "Embedding of hypercubes into banana trees," Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 92, pp. 147–157, 2015.
S. Rajeshwari and M. Rajesh, "Exact wirelength of embedding 3-ary n-cubes into certain cylinders and trees," Fundamenta Informaticae, vol. 188, pp. 269–284, 2022.
A. B. Greeni, R. S. Rajan, and P. Immanuel, "Embedding augmented cube into certain trees and windmill graphs," International Journal of Foundations of Computer Science, vol. 35, pp. 409–434, 2024.
P. Manuel, I. Rajasingh, B. Rajan, and H. Mercy, "Exact wirelength of hypercube on a grid," Discrete Applied Mathematics, vol. 157, pp. 1486–1495, 2009.
G. C. Vincy and M. D. Raj, "Minimum linear arrangement and embedding of (K₁₁ - C₁₁)ⁿ into specific graphs with optimal wirelength calculation," The Journal of Supercomputing, vol. 81, 2025.
P. Immanuel and A. B. Greeni, "Optimization of layout for embedding half hypercube into conventional tree architectures," Concurrency and Computation: Practice and Experience, vol. 36, 2024.
R. Guo, Y. Wang, J. Fan, and W. Fan, "Embedding hierarchical cubic networks into rooted complete binary trees for minimum wirelength," International Journal of Foundations of Computer Science, vol. 35, pp. 327–352, 2024.
P. Immanuel and A. B. Greeni, "Optimizing the layout of embedding BCube into grid architectures," Journal of Parallel and Distributed Computing, vol. 201, 105070, 2025.
R. Dominic, R. S. Rajan, T. M. Rajalaxmi, and L. Packiaraj, "Optimal layout of embedding onto folded hypercubes," International Journal of Foundations of Computer Science, 2025. doi.org/10.1142/S0129054125500066
R. S. Rajan, R. M. Reji, and T. M. Rajalaxmi, "An upper bound for edge congestion and the exact wirelength of embedding onto BC graphs," International Journal of Foundations of Computer Science, 2025. doi.org/10.1142/S0129054125500224
R. S. Rajan, R. Dominic, and N. Sadagopan, "Optimal layout of (Kₚ - Cₚ)ⁿ into wheel like networks," Journal of Interconnection Networks, vol. 25, 2450007, 2025.
R. M. Reji, R. S. Rajan, and T. M. Rajalaxmi, "Embedding Knodel graph into cube like architectures: Dilation optimization and wirelength analysis," Journal of Interconnection Networks, vol. 24, 2350031, 2024.
R. S. Rajan, A. B. Greeni, and P. L. Joshwa, "Maximum subgraph problem and minimum linear arrangement of generalized sierpinski graphs," Journal of Graph Algorithms and Applications, vol. 27, pp. 767–782, 2023.
R. Guo, Y. Wang, J. Fan, and W. Fan, "Embedding hierarchical folded cubes into linear arrays and complete binary trees with minimum wirelength," The Journal of Supercomputing, vol. 79, pp. 11300–11327, 2023.
P. L. Joshwa, R. S. Rajan, T. M. Rajalaxmi, and I. N. Gangul, "Embedding of extended sierpinski networks S⁺⁺(k,m) into certain trees," RAIRO-Operations Research, 2025. doi:10.1051/ro/2025085
R. S. Rajan, R. Dominic, and T. M. Rajalaxmi, "Graph embedding for minimum wirelength in circulant networks: Applications in architecture simulation and comparative analysis," Journal of Interconnection Networks, 2025. doi.org/10.1142/S0219265925500082
R. Dominic, R. S. Rajan, and T. M. Rajalaxmi, "Optimizing wirelength in graph embedding: Folded hypercube into fan and windmill networks: A comparative study," Applied Computational Mathematics, pp. 65–72, 2024. doi.org/10.1007/978-3-031-77764-6_8
R. S. Rajan, P. Manuel, and I. Rajasingh, "Embeddings between Hypercubes and Hypertrees," Journal of Graph Algorithms and Applications, vol. 19, pp. 361–373, 2015.
P. L. Joshwa, R. S. Rajan, and T. M. Rajalaxmi, "Maximum subgraph and wirelength optimization in cyclic bipartite networks G_{k,3}," International Journal of Parallel, Emergent and Distributed Systems, pp. 1–21, 2026. doi.org/10.1080/17445760.2025.2610814
P. L. Joshwa, R. S. Rajan, and T. M. Rajalaxmi, "Maximum subgraph and wirelength analysis of extended Sierpiński networks in parallel computing," Discrete Applied Mathematics, vol. 383, pp. 367–382, 2026.
N. Cohen, D. Dimitrov, R. Krakovski, R. Skrekovski, and V. Vukasinovic, "On Wiener index of graphs and their line graphs," MATCH Communications in Mathematical and in Computer Chemistry, vol. 64, pp. 683–698, 2010.
M. S. Sardar, S. Zafar, and Z. Zahid, "Computing topological indices of the line graphs of banana tree graph and firecracker graph," Applied Mathematics and Nonlinear Sciences, vol. 2, pp. 83–92, 2017.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.