Minimum linear arrangement and embedding of (K₁₁ − C₁₁)ⁿ into specific graphs with optimal wirelength calculation

Interconnection networks, composed of numerous integrated circuits (ICs), form complex structures crucial to many parallel computing systems. The effectiveness of very large scale integration (VLSI) relies on various parameters that influence the design’s cost. In this article, one such crucial parameter, called wirelength, has been studied. Graph embedding is a tool used in the design of VLSI layouts. A graph’s optimal linear layout, also known as minimum linear arrangement (MinLA), is achieved by embedding its vertices onto a line topology. The network topology of \((K_{11} - C_{11})^{n}\) ${(K_{11}-C_{11})}^n$ is significant due to its distinct structure when \(n=1\) $n=1$ . The study of the Cartesian product of graphs, whether considered as a guest graph (Bezrukov et al. in Ann Comb 4:153–169, 2000; Arockiaraj et al. in Theor Comput Sci 905:69–86, 2022), a host graph (Harper in J Soc Ind Appl Math 12:131–135, 1964; Arockiaraj et al. in Discret Appl Math 288:50–65, 2021), or in relation to solving its edge isoperimetric problem (EIP) (Bonnet and Sikora in Int J Found Comput Sci 27:771–774, 2016; Afiya and Rajesh in J Supercomput 79:12000–12012, 2023), has received considerable attention in recent years. This has also motivated the study of the cartesian product of \((K_{11} - C_{11})\) $(K_{11}-C_{11})$ . The paper focuses on computing the EIP of \((K_{11} - C_{11})^{n}\) ${(K_{11}-C_{11})}^n$ and addresses the minimum linear arrangement and optimal wirelength of grid, triangular snake and certain tree structures.