Optimization of layout for embedding complete k-partite graphs into line graphs of certain tree architectures

Electronic Journal of Graph Theory and Applications

N. Jothilakshmi^a, R. Sundara Rajan^b, Indra Rajasingh^c, Joe Ryan^d

jothi.jaya123@gmail.com, vprsundar@gmail.com (corresponding author), indrarajasingh@yahoo.com, 2fryan@gmail.com

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 [1], 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: embedding, congestion, wirelength, complete k-partite graph, line graph, complete k-ary tree, banana tree, firecrackers tree.

Mathematics Subject Classification: 05C05, 05C60, 05C76, 05C69

DOI: 10.5614/ejgta.2026.14.1.12

Received: 22 August 2025, Revised: 10 January 2026, Accepted: 11 February 2026.

^&lt;sup>a</sup>Department of Mathematics, Hindustan Institute of Technology and Science, Chennai - 603 103, India

^&lt;sup>b</sup>Department of Mathematics, Rajalakshmi Engineering College, Chennai - 602 105, India

^&lt;sup>c</sup>Department of Mathematics, Saveetha School of Engineering, SIMATS, Chennai - 602 105, India

^&lt;sup>d</sup>School of Information and Physical Sciences, The University of Newcastle, NSW 2308, Australia

1. Introduction

Recent progress in integrated circuits has made it possible to build interconnection networks, leading to the study and analysis of various interconnection topologies. These networks are commonly represented as graphs, with graph embedding serving as a key factor in their evaluation. Graph embedding is particularly significant in parallel computing applications, including data structures and network design. Several cost factors are considered when assessing embedding efficiency, with wirelength being the most important. Other crucial metrics include dilation, edge congestion, wirelength, load, and expansion [1].

Dilation is the shortest distance in the Y graph between any two vertices equivalent to neighboring vertices in the X graph. Edge congestion is the maximum number of edges from the X graph mapped onto a single edge of the Y graph. In several fields, including data structures, biological models that use parallel architectures, and VLSI design, wirelength is crucial [1].

Complete k-partite graphs are a natural generalization of fully linked networks, which correspond to complete graphs. In such graphs, the vertex set is partitioned into k disjoint independent sets, with edges connecting all possible pairs of vertices that belong to different sets. Numerous research works have examined embedding parameters for complete multipartite graphs [2–5]. A complete k-partite graph is commonly denoted by K^p1,p2,...,p^k where each pⁱ represents the cardinality of the i-th part [6]. Turán graphs are of great importance among such graphs. For positive integers n and k, the Turán graph T(n, k) is the unique complete k-partite graph on n vertices, where the sizes of the parts are as balanced as possible, meaning the sizes of any two parts differ by no more than one. Developed initially in extremal graph theory, Turán graphs also find applications in various other mathematical and applied areas [2].

A tree is a fundamental structure in graph theory, defined as a connected graph with no cycles. This means that for every pair of vertices, there is exactly one path connecting them. Trees are the simplest type of connected graphs and are frequently used to model hierarchical systems. In a tree with n vertices, there are always n − 1 edges, and a unique path exists between any two vertices [7].

The line graph method is a powerful technique for constructing a larger graph from a given one. This method allows the resulting graph to inherit several important properties from the original graph, including degree, diameter, connectivity, eulericity, and hamiltonicity. It has been extensively applied in the design of interconnection networks. Given a graph T, its line graph L(T) is formed by representing each edge of T as a vertex in L(T), where adjacency in L(T) corresponds to edges in T sharing a common end vertex [8]. An important characteristic of the line graph of a tree is that it is always a chordal graph. A graph is said to be chordal if every induced cycle in the graph is a triangle [9].

Line graphs naturally arise in various embedding problems due to their ability to represent edge-adjacency relationships of an original graph. While embedding has been studied for many classical network topologies, such as trees, meshes, and hypercubes, problems involving line graphs present significant algorithmic challenges. Recently, Barth et al. investigated the problem of correcting a general graph into a line graph by minimizing the Hamming distance. They proved that this problem is NP-complete and also showed that it is fixed-parameter tractable (FPT) when parameterized by the treewidth of the input graph. This result highlights the structural and

computational complexity of line graph transformations, reinforcing the challenges in embedding or editing graphs to conform to line graph properties [10].

Studies on graph embedding have been well studies in the literature [2–5, 10–31]. For instance, embeddings of complete multipartite graphs into circulant, wheel, path, cycle, hypertree, cylinder, and torus networks have been studied [3], embeddings \((K_9 - C_9)^n\) into certain tree structures [11], embeddings complete bipartite graph into grid networks [4], and complete multipartite graphs into cartesian products of paths and cycles [12], Turán graphs into incomplete hypercubes [2] and complete binary trees [5], Hypercubes into banana trees [13], half hypercube into tree architectures [18], cubic networks into rooted complete binary trees [19], folded hypercubes into tree like architectures [21], hierarchical folded cubes into linear arrays and complete binary trees [26], sierpinski networks into certain trees [27], circulant networks into certain tree networks and the star of cycle [28]. Cyclic bipartite networks into tree-like architectures [31]. However, line graphs have not yet been investigated as host graphs in this context. In this work, we address this gap by considering the line graphs of k-ary trees, banana trees, and firecracker trees as host graphs, and we derive the exact wirelength for the embedding of complete multipartite graphs into these networks.

2. Basic Concepts

The essential definitions and lemmas are listed below.

Definition 2.1. Let X and Y be finite graphs. An embedding of X into Y is a pair \((h, P_h)\) defined as follows.

• 1. h is a one to one map: \(V(X) \rightarrow V(Y)\)
• 2. \(P_h\) is a one to one map from E(X) to \(\{P_h(e) : P_h(e) \text{ is a path in } Y \text{ between } h(u) \text{ and } h(v) \text{ for } e = (uv) \in E(X)\}.\)

For brevity, we denote the pair \((h, P_h)\) as h.

Definition 2.2. Let h be an embedding of X into Y. For \(e = (uv) \in E(X)\), then,

\[dil_h(X, Y, e) = |P_h(e)|;\]
\[dil_h(X, Y) = \max_{e \in E(X)} dil_h(X, Y, e);\]
\[dil(X, Y) = \min_h dil_h(X, Y).\]

Definition 2.3. Let h be an embedding of X into Y. For \(e' = (u'v') \in E(Y)\), then,

\[EC_h(X, Y, e') = |e \in E(X) : e' \in P_h(e)|;\] \[EC_h(X, Y) = \max_{e' \in E(Y)} EC_h(X, Y, e');\] \[EC(X, Y) = \min_{h} EC_h(X, Y).\]

Figure 1. An embedding h from X into Y with \(dil_h(X,Y) = 5\), \(EC_h(X,Y) = 5\), and \(WL_h(X,Y) = 19\)

Definition 2.4. The wirelength of an embedding h from X into Y is given by,

\[WL_h(X,Y) = \sum_{e' \in E(Y)} EC_h(X,Y,e') = \sum_{e \in E(X)} dil_h(X,Y,e);\]\[WL(X,Y) = \min_h WL_h(X,Y).\]

If Z is any subset of E(Y), then \(EC_h(Z) = \sum_{e \in Z} EC_h(e)\). Fig 1 illustrates the concepts of dilation, congestion, and wirelength in an embedding h: X to Y. It is evident that in an embedding of the graph X into Y, the sum of the dilations is equal to the sum of the congestions which is the wirelength. Here, the wirelength is derived by summing the congestion values.

Let \(S \subseteq V(X)\), then

• \[I_X(S) = \{(uv) \in E \mid u, v \in S\}, \ I_X(b) = \max_{S \subseteq V, |S| = b} |I_X(S)|;\]

• \[\theta_X(S) = \{(uv) \in E \mid u \in S, v \notin S\}, \ \theta_X(b) = \min_{S \subseteq V, |S| = b} |\theta_X(S)|.\]

For \(b=1,2,\ldots,n=|V(x)|\), the task of identifying a subset \(S\subseteq V(X)\) with |S|=b and \(|I_X(S)|=I_X(b)\) is referred to as the maximum subgraph problem. Such subsets are called optimal. Similarly, for \(b=1,2,\ldots,n\), the problem of finding a subset \(S\subseteq X\) with |S|=b and \(|\theta_X(S)|=\theta_X(b)\) is known as the minimum cut problem.

In a regular graph, the functions \(I_X\) and \(\theta_X\) are closely related such that solving one provides the solution to the other. Specifically, for any regular graph with regularity r, \(2I_X(b) + \theta_X(b) = rb\), \(b = 1, 2, \ldots, n\). For complete k-partite graphs the maximum subgraph problem was determined in [3] and is stated as follows:

Theorem 2.1. [3] Let X represent a complete k-partite graph \(K_{r,r,\dots,r}\) with n = kr vertices, where \(k \geq 2\) and \(r \geq 2\). The maximum number of edges in a subgraph of X with a' vertices is given by:

\[I_X(a) = \begin{cases} \frac{a(a-1)}{2} & \text{if } a \le k-1; \\ \frac{q^2k(k-1)}{2} & \text{if } a = qk, \ 1 \le q \le r; \\ \frac{(q-1)^2k(k-1)}{2} + i(q-1)(k-1) + \frac{i(i-1)}{2} & \text{if } a = (q-1)k+i, \ 1 \le i \le k-1, \\ 2 \le q \le r. \end{cases}\]

Definition 2.5. [33] The line graph L(X) of a graph X is described as follows.

• Each vertex in L(X) corresponds to an edge of X.
• Two vertices in L(X) are adjacent if and only if the edges they represent in X share a common vertex.

Definition 2.6. [8] Let X be a graph and S ⊆ E(X) be an edge cut if X \S disconnects the graph X into more than one connected component.

Definition 2.7. [1] Let X be a graph and S ⊆ E(X), E(X) \ S disconnect the graph into more than one component, say C1, C2, . . . , C^l , where l ≤ |V (X)|. A component Cⁱ , for 1 ≤ i ≤ l, is called a convex component if all shortest paths between every pair of vertices in Cⁱ must lie within the same component Cⁱ .

Definition 2.8. [9] A cycle C of length greater than three is said to be a chordless cycle if there is no chord in C. A graph X is said to be chordal if there is no chordless cycle of length greater than three.

Definition 2.9. [8] Let X = (V, E) be a graph, and let S ⊆ V . The induced subgraph of X by S, denoted X[S], is the subgraph with vertex set S and edge set consisting of all edges in X whose endpoints are both in S.

Lemma 2.1. [2] Let h be an embedding from the graph X into the graph Y , where |V (X)| = |V (Y )|. Let the edge cut of Y be denoted by S, such that by removing S, the graph Y is separated into exactly two connected components, Y¹ and Y2, and X¹ = X[h −1 (V (Y1))] and X² = X[h −1 (V (Y2))]. Additionally, let S fulfill the subsequent requirements:

• (i) For each e = (uv) ∈ E(Xi), where i ∈ {1, 2}, the path Ph(e) contains no edges in S.
• (ii) For each e = (uv) ∈ E(X), where u ∈ V (X1) and v ∈ V (X2), the path Ph(e) contains exactly one edge in S.
• (iii) V (X1) and V (X2) are optimal sets, In other words, E(X1) and E(X2) are the minimum subgraph of X with the cardinality of V (X1) and V (X2), respectively.

Then ECh(S) is the minimum across all embeddings h from X into Y and

\[EC_h(S) = \sum_{u \in V(X_1)} \deg_X(u) - 2|E(X_1)| = \sum_{u \in V(X_2)} \deg_X(u) - 2|E(X_2)|.\]

Lemma 2.2. [2] Let h be an embedding of X into Y . Assume that {S1, S2, . . . , Sl} is a partition of [2E(Y )], where [2E(Y )] is the collection of all edge of Y repeated exactly twice and each subset S^j represents an edge cut of Y and satisfies the Lemma 2.1. Thus

\[WL_h(X,Y) = \frac{1}{2} \left[ \sum_{j=1}^{l} EC_h(S_j) \right].\]

3. Main Results

In this section, we embed complete k-partite graphs into certain families of chordal graphs, which are obtained by taking the line graph of certain trees.

3.1. Line Graph of Complete k-ary Tree

A k-ary tree is a rooted tree where each vertex has at most k children. When constructing the line graph of a k-ary tree, each edge of the tree becomes a vertex in the line graph, and two such vertices are connected if the corresponding edges in the original tree share a vertex. This line graph captures how the original edges are structurally linked in the tree.

Definition 3.1. [7] The complete k-ary tree of level l, denoted by \(CT_l^k\), is a tree in which each internal vertex has exactly k children, and the tree has a level l. The root is located at level l, and all leaf vertices are at level l. Thus \(CT_l^k\) has exactly \(\frac{k^{l+1}-1}{k-1}\) vertices and \(\frac{k^{l+1}-k}{k-1}\) edges.

Note that, for any k and l, the number \(\frac{k^{l+1}-k}{k(k-1)}\) is a natural number \(\mathbb{N}\), since \(\frac{k^{l+1}-k}{k(k-1)}=\frac{k^l-1}{k-1}=1+k+\cdots+k^{l-1}\in\mathbb{N}\).

Embedding Algorithm A

Input: The complete k-partite graph \(K_{p_1,p_2,\dots,p_k}\) with \(|p_i| = |p_j|\) for all \(i, j, 1 \le i < j \le k\), and a line graph of complete k-ary tree of level \(l, L(CT_l^k), k \ge 2, l \ge 2\).

Algorithm: Let \(V_1, V_2, \ldots, V_k\) be a partition of the complete k-partite graph and label the vertices of \(V_i, 1 \le i \le k\) as \(jk + i, j = 0, 1, \ldots, \frac{k^l - k}{k - 1}\). Label the vertices of \(L(CT_l^k)\) as follows:

• (i) Let \(l: E(CT_l^k) \to \mathbb{N}\), label the edge e between the levels (i-1,i), where \(1 \le i \le l\), in \(CT_l^k\) as \(\frac{k^i-k}{k-1}+1, \frac{k^i-k}{k-1}+2, \ldots, \frac{k^{i+1}-k}{k-1}\), from the left-most child to the right-most child, respectively.
• (ii) Let \(f: V(L(CT_l^k)) \to \mathbb{N}\), label the vertex \(x = L(e) \in V(L(CT_l^k))\) by f(x = L(e)) = l(e). For illustration, the vertex labeling of \(L(CT_4^3)\) is given in Fig. 2.

Output: An embedding h of \(K_{p_1,p_2,\ldots,p_k}\) with \(|p_i| = |p_j|\) for all \(i, j, 1 \le i < j \le k\), into \(L(CT_l^k)\) defined as h(x) = x, with exact wirelength.

Proof of correctness: Let v be a vertex in level i of \(CT_l^k\), \(i=1,2,\ldots,l-1\). Let the subtree rooted at \(v_j\) be denoted by \(ST_i(v_j)\), \(i=1,2,\ldots,l-1\), \(j=1,2,\ldots,k^i\). Let \(S_i^k(j)\) be the edge cut in \(L(CT_l^k)\) whose removal disconnects \(L(CT_l^k)\) into two connected components, say \(Y_i^k(j)\) and \(\overline{Y_i^k(j)}\), where \(Y_i^k(j)\) is isomorphic to \(L(ST_i(v_j) \cup \{e\})\), e is an edge incident to \(v_j\) and \(e \not\in E(ST_i(v_j))\). Let \(X_i^k(j) = X[h^{-1}(V(Y_i^k(j)))]\) and \(\overline{X_i^k(j)} = X[h^{-1}(V(\overline{Y_i^k(j)}))]\). Since \(X_i^k(j)\) is an optimal set by the labeling of the complete k-partite graph. Also \(S_i^k(j)\) satisfies the Lemma 2.1. Hence, \(EC_h(S_i^k(j))\) achieves its minimum value and is given by

\[EC_h(S_i^k(j)) = (k^l - k^{l-i}) \left(\frac{k^{l-i+1} - k}{k-1}\right) + k^l - 2k^{l-i} + 1.\]

Figure 2. Vertex labeling of \(L(CT_4^3)\) obtained from the edge labeling of \(CT_4^3\). The labeling ensures that the induced vertex sets form optimal sets by applying Lemma 11.

Let \(T_i^k(j)\), \(i=1,2,\ldots,l-1\), \(j=1,2,\ldots,k^i\) be the edge cut in \(L(CT_l^k)\) whose removal disconnects \(L(CT_l^k)\) into two connected components, say \(Y_i^k(j)\) and \(\overline{Y_i^k(j)}\), where \(Y_i^k(j)\) is isomorphic to \(L(ST_i(v_j))\). Let \(X_i^k(j)=X[h^{-1}(V(Y_i^k(j)))]\) and \(\overline{X_i^k(j)}=X[h^{-1}(V(\overline{Y_i^k(j)}))]\). \(X_i^k(j)\) is an optimal set by the labeling of the complete k-partite graph. Also \(T_i^k(j)\) satisfies the Lemma 2.1. Hence, \(EC_h(T_i^k(j))\) achieves its minimum value and is given by

\[EC_h(T_i^k(j)) = (k^l - k^{l-i}) \left(\frac{k^{l-i+1} - k}{k-1}\right).\]

Let \(S_l^k(j)\), \(j=1,2,\ldots,k^l\) be the edge cut in \(L(CT_l^k)\) whose removal disconnects \(L(CT_l^k)\) into two connected components, say \(Y_l^k(j)\) and \(\overline{Y_l^k(j)}\), where \(Y_l^k(\underline{j})\) is isomorphic \(L(\underline{e_j})\), \(\underline{e_j}\) is the \(j^{th}\) pendent edge in \(CT_l^k\). Let \(X_l^k(j)=X[h^{-1}(V(Y_l^k(j)))]\) and \(\overline{X_l^k(j)}=X[h^{-1}(V(\overline{Y_l^k(j)}))]\). Since \(X_l^k(j)\) is an optimal set, each \(S_l^k(j)\) satisfies the Lemma 2.1. Hence \(EC_h(S_l^k(j))\) achieves its minimum value and is given by

\[EC_h(S_l^k(j)) = k^l - 1.\]

The edge cut \(S_i^k(j) \cup T_i^k(j) \cup S_l^k(j)\), \(i=1,2,\ldots,l-1\), \(j=1,2,\ldots,k^i\) constitutes all the edges of \(L(CT_l^k)\) twice and is a partition of \([2E(L(CT_l^k))]\). Then by Lemma 2.2, the wirelength is minimum.

Theorem 3.1. The minimum wirelength of embedding \(K_{p_1,p_2,...,p_k}\) into \(L(CT_l^k)\), where \(|p_i|=|p_j|=|p_j|\)

k ^l−1 k−1 for all i, j, 1 ≤ i < j ≤ k, k ≥ 2 and l ≥ 2 is given by

\[WL(K_{p_1,p_2,\dots,p_k},L(CT_l^k)) = \frac{1}{2} \left[ \sum_{i=1}^l \left[ \left( k^{l+i} - k^l \right) \left( \frac{k^{l-i+1} - k}{k-1} \right) + k^i \left( k^l + 1 \right) - 2k^l \right] + \sum_{i=1}^{l-1} \left[ \left( k^{l+i} - k^l \right) \left( \frac{k^{l-i+1} - k}{k-1} \right) \right] \right].\]

Proof. Label the vertices of K^p1,p2,...,p^k with |pⁱ | = |p^j | for all i, j, 1 ≤ i < j ≤ k, and L(CT^k l ) using Embedding Algorithm A. Then by Lemma 2.2, the wirelength is given by

\[\begin{split} WL\bigg(K_{p_1,p_2,\dots,p_k},L(CT_l^k)\bigg) &= \frac{1}{2} \left[ \sum_{j=1}^{k^i} \left[ \sum_{i=1}^{l} \left[ \left( k^l - k^{l-i} \right) \left( \frac{k^{l-i+1} - k}{k-1} \right) + k^l - 2k^{l-i} + 1 \right] \right. \\ &+ \sum_{i=1}^{l-1} \left[ \left( k^l - k^{l-i} \right) \left( \frac{k^{l-i+1} - k}{k-1} \right) \right] \right] \\ &= \frac{1}{2} \left[ \sum_{i=1}^{l} \left[ \left( k^{l+i} - k^l \right) \left( \frac{k^{l-i+1} - k}{k-1} \right) + k^{l+i} - 2k^l + k^i \right] \right. \\ &+ \sum_{i=1}^{l-1} \left[ \left( k^{l+i} - k^l \right) \left( \frac{k^{l-i+1} - k}{k-1} \right) \right] \right] \\ &= \frac{1}{2} \left[ \sum_{i=1}^{l} \left[ \left( k^{l+i} - k^l \right) \left( \frac{k^{l-i+1} - k}{k-1} \right) + k^i \left( k^l + 1 \right) - 2k^l \right] \right. \\ &+ \sum_{i=1}^{l-1} \left[ \left( k^{l+i} - k^l \right) \left( \frac{k^{l-i+1} - k}{k-1} \right) \right] \right] \\ &= \sum_{i=1}^{l-1} \left( k^{l+i} - k^l \right) \left( \frac{k^{l-i+1} - k}{k-1} \right) + \frac{1}{2} \sum_{i=1}^{l} \left( k^i (k^l + 1) - 2k^l \right). \end{split}\]

3.2. Line Graph of Banana Tree

A banana tree is the graph obtained by attaching several star graphs to a central vertex or to each vertex of a short path. Essentially, it resembles several star graphs hanging off a main structure. The line graph of a banana tree represents the overlap of edges at shared vertices, particularly at the central vertex of each star and where multiple stars connect.

Definition 3.2. A banana tree Bk,n [34], is constructed by connecting one leaf from each of n copies of a k-star graph to a unique root vertex, which is distinct for each star. The graph Bk,n has nk + 1 vertices and nk edges.

Definition 3.3. Let T = (V, E) be a rooted tree with vertex set V and edge set E. Each edge \(e = (uv) \in E\) is directed from parent u to child v. We define the postorder traversal of edges as follows: An edge e = (uv) is visited only after all edges (vw) where w is a child of v (i.e., all child edges of e) have been visited, see Fig. e(e) and e(e).

Embedding Algorithm B

Input: The complete k-partite graph \(K_{p_1,p_2,\ldots,p_k}\) with \(|p_i| = |p_j|\) for all \(i, j, 1 \le i < j \le k\), \(k \ge 3\) and a line graph of banana tree \(L(B_{k,n}), k \ge 3, n \ge 4\).

Algorithm: Let \(V_1, V_2, \ldots, V_k\) be a partition of the complete k-partite graph and label the vertices of \(V_i, 1 \le i \le k\) as \(jk + i, j = 0, 1, \ldots, n - 1\). Label the vertices of \(L(B_{k,n})\) by using the postorder edge traversal. For illustration, the edge labeling of \(B_{k,n}\) and the vertex labeling of \(L(B_{k,n})\) are given in Fig. 4 and 5 with \(f(x = L(e)) = l(e), e \in E(B_{k,n})\).

Figure 3. (a) Postorder edge traversal (b) Labeling of a tree using postorder edge traversal

Output: An embedding h of \(K_{p_1,p_2,\ldots,p_k}\) with \(|p_i| = |p_j|\) for all \(i, j, 1 \le i < j \le k\), into \(L(B_{k,n})\) defined as h(x) = x, with exact wirelength.

Proof of correctness: Let v be a vertex at the first level of \(B_{k,n}\). Let the subtree rooted at \(v_j\) be denoted by \(ST_1(v_j)\), \(j=1,2,\ldots,k\). Let \(S_1(j)\) be the edge cut in \(L(B_{k,n})\) whose removal disconnects \(L(B_{k,n})\) into two connected components, say \(Y_1(j)\) and \(\overline{Y_1(j)}\), where \(Y_1(j)\) is isomorphic to \(L(ST_1(v_j)\cup\{e\})\), e is an edge incident to \(v_j\) and \(e\not\in E(ST_1(v_j))\). Let \(X_1(j)=X[h^{-1}(V(Y_1(j)))]\) and \(\overline{X_1(j)}=X[h^{-1}(V(\overline{Y_1(j)}))]\). Then \(|V(X_1(j))|=n\) and \(|V(\overline{X_1(j)})|=n(k-1)\). By the labeling of the complete k-partite graph, this forms an optimal set, leading to the expression: \(I_G(n)=\frac{m^2k(k-1)}{2}+m(n-mk)(k-1)+\binom{n-mk}{2}\). Further, \(S_1(j)\) satisfies the Lemma 2.1. Hence, \(EC_h(S_1(j))\) achieves its minimum value.

Let \(T_1(j), j=1,2,\ldots,k\) be the edge cut in \(L(B_{k,n})\) whose removal disconnects \(L(B_{k,n})\) into two connected components, say \(Y_1(j)\) and \(\overline{Y_1(j)}\), where \(Y_1(j)\) is isomorphic to \(L(ST_1(v_j))\). Let \(X_1(j)=X[h^{-1}(V(Y_1(j)))]\) and \(\overline{X_1(j)}=X[h^{-1}(V(\overline{Y_1(j)}))]\). Then \(|V(X_1(j))|=n-1\) and \(|V(X_1(j))|=n(k-1)-1\). By the labeling of the complete k-partite graph, this forms an optimal set, leading to the expression: \(I_G(n-1)=\frac{m^2k(k-1)}{2}+m(n-mk-1)(k-1)+\binom{n-mk-1}{2}\). Further, \(T_1(j)\) satisfies the Lemma 2.1. Hence, \(EC_h(T_1(j))\) attains its minimum value. The edge cut \(S_2(j)\) is same as \(T_1(j), j=1,2,\ldots,k\). Thus \(EC_h(S_2(j))=EC_h(T_1(j))\).

Let \(T_2(j)\), \(j=1,2,\ldots,k\) be the edge cut in \(L(B_{k,n})\) whose removal disconnects \(L(B_{k,n})\) into two connected components, say \(Y_2(j)\) and \(\overline{Y_2(j)}\), where \(Y_2(j)\) is isomorphic to \(L(ST_2(v_j))\). Let \(X_2(j)=X[h^{-1}(V(Y_2(j)))]\) and \(\overline{X_2(j)}=X[h^{-1}(V(\overline{Y_2(j)}))]\). Then \(|V(X_2(j))|=n-2\) and \(|V(\overline{X_2(j)})|=n(k-1)-2\). By the labeling of the complete k-partite graph, this forms an optimal

set, leading to the expression: \(I_G(n-2) = \frac{m^2k(k-1)}{2} + m(n-mk-2)(k-1) + \binom{n-mk-2}{2}\). Further, \(T_2(j)\) satisfies the Lemma 2.1. Hence, \(EC_h(T_2(j))\) achieves its minimum value.

Let \(S_3(j)\), \(j=1,2,\ldots,k(n-2)\) be the edge cut in \(L(B_{k,n})\) whose removal disconnects \(L(B_{k,n})\) into two connected components, say \(Y_3(j)\) and \(\overline{Y_3(j)}\), where \(Y_3(j)\) is isomorphic \(L(e_j)\), \(e_j\) is the \(j^{th}\) pendent edge in \(B_{k,n}\). Let \(X_3(j)=X[h^{-1}(V(Y_3(j)))]\) and \(\overline{X_3(j)}=X[h^{-1}(V(\overline{Y_3(j)}))]\). Since \(X_3(j)\) is an optimal set, each \(S_3(j)\) satisfies the Lemma 2.1. Hence \(EC_h(S_3(j))\) achieves its minimum value.

In general, \(I_G(p) = \frac{m^2k(k-1)}{2} + mp(k-1) + \binom{p}{2}\), where \(n \equiv p \pmod{k}\), and p is given by p = n - mk. Additionally, note that \(\binom{0}{2}\), \(\binom{1}{2}\) and any negative binomial terms will be considered as 0.

The edge cut \(\{S_1(j) \cup T_1(j) \cup S_2(j) \cup T_2(j) : j = 1, 2, \dots, k\} \cup \{S_3(j) : j = 1, 2, \dots, k(n-2)\}\) constitutes all the edges of \(L(B_{k,n})\) twice and is a partition of \([2E(L(B_{k,n}))]\). Then by Lemma 2.2, the wirelength is minimum.

Figure 4. Edge labeling of \(B_{5,6}\) using postorder traversal. This labeling induces the vertex labeling of \(L(B_{5,6})\) used to define the embedding and the edge cuts applied in Lemma 11.

Figure 5. Vertex labeling of \(L(B_{5,6})\) induced by the postorder edge labeling of \(B_{5,6}\). The labeling ensures that the induced vertex sets form optimal sets required for applying Lemma 11 in the wirelength computation.

Theorem 3.2. The minimum wirelength of embedding \(K_{p_1,p_2,\ldots,p_k}\) with \(|p_i|=|p_j|\) for all i, j,

1 ≤ i < j ≤ k, into L(Bk,n), where k ≥ 3 and n ≥ 4 is given by

\[WL\left(K_{p_1,p_2,...,p_k}, L(B_{k,n})\right) = \frac{k}{2} \left[ (k-1) \left[ 5n^2 - 6n + 4m^2k - 8mn + 8m \right] - 2\binom{n-mk}{2} - 4\binom{n-mk-1}{2} - 2\binom{n-mk-2}{2} \right].\]

Proof. Label the vertices of K^p1,p2,...,p^k with |pⁱ | = |p^j | for all i, j, 1 ≤ i < j ≤ k, and L(Bk,n) using Embedding Algorithm B. By Lemma 2.1, the edge congestion of the edge cuts are as follows:

• \[EC_h(S_1(j)) = n^2(k-1) - 2\left[\frac{m^2k(k-1)}{2} + m(n-mk)(k-1) + \binom{n-mk}{2}\right], j = 1, 2, \dots, k.\]

• \[EC_h(T_1(j)) = EC_h(S_2(j)) = n(n-1)(k-1) - 2\left[\frac{m^2k(k-1)}{2} + m(n-mk-1)(k-1) + \binom{n-mk-1}{2}\right], j = 1, 2, \dots, k.\]

• \[EC_h(T_2(j)) = n(n-2)(k-1) - 2\left[\frac{m^2k(k-1)}{2} + m(n-mk-2)(k-1) + \binom{n-mk-2}{2}\right],\]
\(j = 1, 2, \dots, k.\)

• \[EC_h(S_3(j)) = n(k-1), j = 1, 2, \dots, k(n-2).\]

By Lemma 2.2, the wirelength is given by

\[WL\left(K_{p_1,p_2,\ldots,p_k},L(B_{k,n})\right)\]

\[= \frac{1}{2} \left[ \sum_{j=1}^{k} \left[ n^{2}(k-1) - 2 \left[ \frac{m^{2}k(k-1)}{2} + m(n-mk)(k-1) + \binom{n-mk}{2} \right] \right] + 2 \left[ \sum_{j=1}^{k} \left[ n(n-1)(k-1) - 2 \left[ \frac{m^{2}k(k-1)}{2} + m(n-mk-1)(k-1) + \binom{n-mk-1}{2} \right] \right] \right] + \sum_{j=1}^{k} \left[ n(n-2)(k-1) - 2 \left[ \frac{m^{2}k(k-1)}{2} + m(n-mk-2)(k-1) + \binom{n-mk-2}{2} \right] \right] + \sum_{j=1}^{k(n-2)} n(k-1) \right]\]

Embedding complete k-partite graphs into line graph of tree architectures | N. Jothilakshmi et al.

\[\begin{split} &=\frac{1}{2}\Bigg[n^2k(k-1)-2k\bigg[\frac{m^2k(k-1)}{2}+m(n-mk)(k-1)+\binom{n-mk}{2}\bigg]\\ &+2nk(n-1)(k-1)-4k\bigg[\frac{m^2k(k-1)}{2}+m(n-mk-1)(k-1)+\binom{n-mk-1}{2}\bigg]\\ &+nk(n-2)(k-1)-2k\bigg[\frac{m^2k(k-1)}{2}+m(n-mk-2)(k-1)+\binom{n-mk-2}{2}\bigg]\bigg]\\ &+nk(n-2)(k-1)\Bigg]\\ &=\frac{1}{2}\Bigg[k(k-1)(5n^2-6n)-k(k-1)\bigg[m^2k+2m(n-mk)+2m^2k+4m(n-mk-1)\\ &+m^2k+2m(n-mk-2)\bigg]-2k\bigg[\binom{n-mk}{2}+2\binom{n-mk-1}{2}+\binom{n-mk-2}{2}\bigg]\bigg]\\ &=\frac{k}{2}\bigg[(k-1)\bigg[5n^2-6n+4m^2k-8mn+8m\bigg]\\ &-2\binom{n-mk}{2}-4\binom{n-mk-1}{2}-2\binom{n-mk-2}{2}\bigg]. \end{split}\]

3.3. Line Graph of Firecrackers Tree

A firecracker tree can be visualized as a sequence of star graphs connected together via their central vertices in a path-like manner, similar to firecrackers connected along a fuse. In constructing its line graph, each edge in the firecracker tree becomes a vertex, and edges that meet at the same vertex are represented by connecting those corresponding vertices in the line graph. The resulting structure highlights the local dense connections of each star and the linear connections between their centers.

Definition 3.4. [34] A firecracker graph Fn,k is formed by concatenating n star graphs Sk, each linked to the next by connecting one of its leaves. The graph Fn,k consists of nk vertices and nk−1 edges.

There is a property that, if X is a complete k-partite graph and T(n, k) is a Turán graph with V (T(n, k)) ⊆ V (X), then V (T(n, k)) is optimal.

Embedding Algorithm C

Input: Turán graph T(nk − 1, k) and a line graph of firecrackers tree L(Fn,k), n ≥ 2, k ≥ 4. Algorithm: Let T(nk − 1, k) be the Turán graph with nk − 1 nodes partitioned into k partite sets V1, V2, . . . , Vk.

• (i) Label the vertices of \(V_i\) as \(j(k-1) + i : j = 0, 1, 2, ..., n-1, 1 \le i \le k-1\)
• (ii) The vertices in \(V_k\) are labelled as \(n(k-1)+1,\ldots,n(k-1)+n-1\).

Label the vertices of the graph \(L(F_{n,k})\), which has |V| = nk - 1 vertices, as follows. The graph consists of:

• (i) A backbone of n-1 connected vertices, denoted as \(b_1, b_2, \ldots, b_{n-1}\) and n copies of a complete graph on k-1 vertices, denoted by \(K_{k-1}^1, K_{k-1}^2, \ldots, K_{k-1}^n\).
• (ii) Each complete graph \(K_{k-1}^i\) is adjacent to the following backbone vertices: For \(2 \le i \le n-1, K_{k-1}^i\) is adjacent to both \(b_{i-1}\) and \(b_i, K_{k-1}^1\) is adjacent to \(b_1, K_{k-1}^n\) is adjacent to \(b_{n-1}\).
• (iii) The vertices of each \(K_{k-1}^i\) are labeled sequentially as: \((k-1)(i-1)+1, (k-1)(i-1)+2, \ldots, (k-1)i\).
• (iv) The backbone vertices are labeled from n(k-1)+1 to n(k-1)+n-1. For illustration, the vertex labeling of \(L(F_{6,5})\) is given in Fig. 6

Figure 6. Vertex labeling of \(L(F_{6,5})\) and the corresponding edge cuts. The labeling scheme defines the embedding of the Turán graph and the edge cuts used in Lemma 11 to derive the exact wirelength.

Output: An embedding h of T(nk-1,k) into \(L(F_{n,k})\) defined as h(x)=x, with exact wirelength.

Proof of correctness: We assume that the labels identify the vertices to which they are assigned. For \(1 \le i \le n-2\), let \(S_i = \{(n(k-1)+i,n(k-1)+i+1),(n(k-1)+i,(i+1)(k-1))\}\) and let \(S_{n-1} = \{(n(k-1)+i,(i+1)(k-1))\}\). Let \(T_1 = \{((k-1),n(k-1)+1)\}\), and for any \(i, 2 \le i \le n-1\), let \(T_i = \{(n(k-1)+i,n(k-1)+i-1),(n(k-1)+i,i(k-1))\}\). Let \(U_1 = \{((k-1),n(k-1)+1)\}\), and for any \(i, 2 \le i \le n-1\), let \(U_i = \{(i(k-1),n(k-1)+i-1),(i(k-1),n(k-1)+i)\}\), and let \(U_n = \{(n(k-1),n(k-1)+n-1)\}\). For any \(i, 1 \le i \le n\), let \(W_i = \{(i(k-1),(k-1)(i-1)+i):1 \le i \le k-2\}\). For any \(i, 1 \le i \le n, 1 \le j \le k-2\), let \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\), and \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\). Then \(\{S_i:1 \le i \le n-1\} \cup \{T_i:1 \le i \le n-1\} \cup \{U_i:1 \le i \le n\} \cup \{W_i:1 \le i \le n\} \cup \{Z_i^j:1 \le i \le n,1 \le j \le k-2\}\) is a partition of \([2E(L(F_{n,k}))]\).

For \(i=1,2,\ldots,n-1\), \(E(L(F_{n,k}))\setminus S_i\) has two connected components \(Y_i\) and \(\overline{Y_i}\), where \(V(Y_i)=\{1,2,\ldots,i(k-1),n(k-1)+1,n(k-1)+2,\ldots,n(k-1)+i\}\). Let \(X_i=X[h^{-1}(V(Y_i))]\) and \(\overline{X_i}=X[h^{-1}(V(\overline{Y_i}))]\). By the labeling of the Turán graph, \(V(Y_i)\) forms an optimal set with

\(|V(Y_i)|\) vertices. Further, the edge cut \(S_i\) satisfies Lemma 2.1. Hence, \(EC_h(S_i)\) attains its minimum value.

For \(E(L(F_{n,k}))\backslash T_1\) has two connected components, say \(Y_1\) and \(\overline{Y_1}\), where \(V(Y_1)=\{1,2,\ldots,(k-1)\}\). Let \(X_1=X[h^{-1}(V(Y_1))]\) and \(\overline{X_1}=X[h^{-1}(V(\overline{Y_1}))]\). By the labeling of the Turán graph, \(V(Y_1)\) forms an optimal set with \(|V(Y_1)|\) vertices. Further, the edge cut \(T_1\) satisfies Lemma 2.1. Hence, \(EC_h(T_1)\) attains its minimum value. For \(i=2,\ldots,n-1\), \(E(L(F_{n,k}))\backslash T_i\) has two connected components, say \(Y_i\) and \(\overline{Y_i}\), where \(V(Y_i)=\{1,2,\ldots,i(k-1),n(k-1)+2-1,n(k-1)+3-1,\ldots,n(k-1)+i-1\}\). Let \(X_i=X[h^{-1}(V(Y_i))]\) and \(\overline{X_i}=X[h^{-1}(V(\overline{Y_i}))]\). By the labeling of the Turán graph, \(V(Y_i)\) forms an optimal set with \(|V(Y_i)|\) vertices. Further, the edge cut \(T_i\) satisfies Lemma 2.1. Hence, \(EC_h(T_i)\) attains its minimum value.

For \(i=1,2,\ldots,n,\ E(L(F_{n,k}))\setminus U_i\) has two connected components, say \(Y_i\) and \(\overline{Y_i}\), where \(\underline{V(Y_i)}=\{(k-1)(i-1)+1,(k-1)(i-1)+2,\ldots,(k-1)i\}\). Let \(X_i=X[h^{-1}(V(Y_i))]\) and \(\overline{X_i}=X[h^{-1}(V(\overline{Y_i}))]\). By the labeling of the Turán graph, \(V(Y_i)\) forms an optimal set with \(|V(Y_i)|\) vertices. Further, the edge cut \(U_i\) satisfies Lemma 2.1. Hence, \(EC_h(U_i)\) attains its minimum value.

For \(i=1,2,\ldots,n\), \(E(L(F_{n,k}))\setminus W_i\) has two connected components, say \(Y_i\) and \(\overline{Y}_i\), where \(\underline{V}(Y_i)=\{(k-1)(i-1)+1,(k-1)(i-1)+2,\ldots,(k-1)i-1\}\). Let \(X_i=X[h^{-1}(V(Y_i))]\) and \(\overline{X}_i=X[h^{-1}(V(Y_i))]\). By the labeling of the Turán graph, \(V(Y_i)\) forms an optimal set with \(|V(Y_i)|\) vertices. Further, the edge cut \(W_i\) satisfies Lemma 2.1. Hence, \(EC_h(W_i)\) attains its minimum value.

For \(i=1,2,\ldots,n,\ j=1,2,\ldots,k-2,\ E(L(F_{n,k}))\setminus Z_i^j\) has two connected components, say \(Y_i^j\) and \(\overline{Y_i^j}\), where \(V(Y_i^j)=\{(k-1)(i-1)+j\}\). Let \(X_i^j=X[h^{-1}(V(Y_i^j))]\) and \(\overline{X_i^j}=X[h^{-1}(V(\overline{Y_i^j}))]\). By the labeling of the Turán graph, \(V(Y_i)\) forms an optimal set with \(|V(Y_i)|\) vertices. Further, the edge cut \(Z_i^j\) satisfies Lemma 2.1. Hence, \(EC_h(Z_i^j)\) attains its minimum value.

Theorem 3.3. The minimum wirelength of embedding T(nk-1,k) into \(L(F_{n,k})\), where \(n \geq 2\), and \(k \geq 4\) is given by

\[WL(T(nk-1,k), L(F_{n,k})) = \frac{1}{2} \left[ \sum_{i=1}^{n-1} \left[ (k-1) \left( i(nk-n-ik-1) + (n-i)(ik-n-1) \right) + n(nk-n) \right] + n \left[ (k-1)(nk-n-k+1) + (k-2)(2nk-2n-k+1) \right] \right].\]

Proof. Label the nodes of T(nk-1,k) and \(L(F_{n,k})\) using Embedding Algorithm C. By Lemma 2.1, the edge congestion of the edge cuts are as follows:

• \[EC_h(S_i) = i \Big[ (k-1)(nk-n-1-ik) + nk-n \Big], i = 1, 2, ..., n-1.\]

Embedding complete k-partite graphs into line graph of tree architectures | N. Jothilakshmi et al.

• \[EC_h(T_i) = (n-i) \left[ (k-1)(ik-n-1) + nk - n \right], i = 1, 2, ..., n-1.\]

• \[EC_h(U_i) = (k-1)(nk-n-k+1), i = 1, 2, ..., n.\]

• \[EC_h(W_i) = (k-2)(nk-n-k+2), i = 1, 2, ..., n.\]

• \[EC_h(Z_i^j) = nk - n - 1, i = 1, 2, \dots, n, j = 1, 2, \dots, k - 2.\]

By Lemma 2.2, the wirelength is given by

\[WL\left(T(nk-1,k),L(F_{n,k})\right) = \frac{1}{2} \left[ \sum_{i=1}^{n-1} \left[ i[(k-1)(nk-n-1-ik)+nk-n] \right] + \sum_{i=1}^{n-1} \left[ (n-i)[(k-1)(ik-n-1)+nk-n] \right] + \sum_{i=1}^{n} \left[ (k-1)(nk-n-k+1) \right] + \sum_{i=1}^{n} \left[ (k-1)(nk-n-k+1) \right] + \sum_{i=1}^{n} \left[ \sum_{j=1}^{k-2} (nk-n-1) \right] \right] = \frac{1}{2} \left[ \sum_{i=1}^{n-1} \left[ (k-1)\left( i(nk-n-1-ik) + (n-i)(ik-n-1) \right) + i(nk-n) + (n-i)(nk-n) \right] + n \left[ (k-1)(nk-n-k+1) + (k-2)(2nk-2n-k+1) \right] \right] = \frac{1}{2} \left[ \sum_{i=1}^{n-1} \left[ (k-1)\left( i(nk-n-ik-1) + (n-i)(ik-n-1) \right) + n(nk-n) \right] + n(nk-n) \right] + n \left[ (k-1)(nk-n-k+1) + (k-2)(2nk-2n-k+1) \right] \right]\]

.

Figure 7. Multilayer VLSI Layout

4. Implementation of VLSI and NoC Design using Graph Embedding Techniques

VLSI: The study of graph embedding is strongly motivated by applications in interconnection network design, particularly in minimizing communication cost measured through wirelength. In this work, we embed complete k-partite graphs into the line graphs of structured host networks such as complete k-ary trees, banana trees, and firecracker trees. While these applications provide practical motivation, the main contribution of this paper remains theoretical, namely, deriving exact wirelength results for these embeddings.

A line graph models adjacency between edges of the original network and naturally represents communication channels or wiring layouts in VLSI systems. Embedding a complete k-partite graph, which commonly represents partitioned task or processor communication patterns, into line graphs of structured networks exploits their regularity and balanced architecture, leading to reduced interconnection distances and lower total wirelength.

In VLSI circuit design, modules and their interconnections are abstracted as vertices and edges see Fig.7. Embedding communication graphs into structured line graph topologies facilitates efficient wiring layouts, reduced congestion, and improved placement of processing units.

NoC: In Network-on-Chip (NoC) architectures, minimizing embedding wirelength directly contributes to lower routing latency and power consumption. Structured host networks such as k-ary trees, banana trees, and firecracker trees provide scalable and predictable communication backbones well suited to these design requirements.

Thus, although VLSI and NoC applications illustrate the relevance of the problem, the emphasis of this study is on establishing exact wirelength results for embeddings of complete k-partite graphs into line graphs of these structured families, which can subsequently inform practical network design decisions.

Overall, embedding complete k-partite graphs into complete k-ary, banana, and firecracker graphs provides a flexible and scalable way to optimize the NoC architecture, offering significant improvements in routing efficiency, power consumption, and system performance [21].

5. Concluding Remarks

In this paper, we have determined the minimum wirelength for embedding complete k-partite graphs into the line graph of a complete k-ary tree, banana tree, firecrackers tree. Our results contribute to the broader understanding of graph embedding, offering precise algorithms and insights that enhance the structural analysis of interconnection networks. The study underscores the importance of mathematical analysis in developing efficient architectures for VLSI and Networkon-Chip (NoC) systems. In [1], we posed as an open problem the determination of wirelength for embeddings of complete multipartite graphs into the line graphs of k-ary trees, banana trees, and firecracker trees. The present study provides explicit embeddings and exact wirelength formulas for all three architectures. Therefore, the open problem stated in [1] is partially resolved by the results of this paper. The embedding techniques developed here may be extended to study wirelength minimization for embeddings into line graph of other tree-like interconnection networks, which remain open for future research.

Acknowledgments

This work is supported by the Anusandhan National Research Foundation (ANRF), Science and Engineering Research Board (SERB), Government of India for funding under the Teachers Associateship for Research Excellence (TARE) scheme with No. TAR/2023/000041. Further, the authors thank the anonymous referees for their valuable comments and suggestions that helped improve the quality of the paper.

References

• [1] 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.
• [2] 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, 25 (2021), 367-381.
• [3] R.S. Rajan, T.M. Rajalaxmi, J.B. Liu, and G. Sethuraman, Wirelength of embedding complete multipartite graphs into certain graphs, Discrete Applied Mathematics, 280 (2020), 221-236.
• [4] A.B. Greeni, and I. Rajasingh, Embedding complete bipartite graph into grid with optimum congesstion and wirelength, International Journal of Networking and Virtual Organisations, 17 (2017), 64-75.
• [5] R.M. Reji, and R.S. Rajan, Optimizing wirelength in embedding Turán graphs into complete binary trees, Springer Proceedings in Mathematics and Statistics, 480 (2025), 3–10.
• [6] N. Obata, Complete multipartite graphs of non-QE class, Electronic Journal of Graph Theory and Applications, 11 (2023), 511–527, doi:10.5614/ejgta.2023.11.2.14.

• [7] M.M. Legese, Steiner Wiener index of complete m-ary trees, Iranian Journal of Mathematical Chemistry, 12, (2021), 101-109.
• [8] J. Xu, Topological structures and analysis of interconnection networks, Kluwer Academic Publishers, Dordrecht (2001).
• [9] V.E. Levit, and D. Tankus, Generating subgraphs in chordal graphs, Discrete Applied Mathematics, 368 (2025), 184-189.
• [10] 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, 28 (2024), 63–90.
• [11] S. Afya, and M. Rajesh, MinLA of (K⁹ − C9) n and its optimal layout into certain trees, The Journal of Supercomputing, 79 (2023), 12000-12012.
• [12] R.S. Rajan, A.A. Shantrinal, T.M. Rajalaxmi, J. Fan, and W. Fan, Embedding complete multipartite graphs into Cartesian product of paths and cycles, Electronic Journal of Graph Theory and Applications, 9 (2021), 507–525.
• [13] J. Quadras, and S.S. Surya, Embedding of hypercubes into banana trees, Journal of Combinatorial Mathematics and Combinatorial Computing, 92 (2015), 147-157.
• [14] S. Rajeshwari, and M. Rajesh, Exact wirelength of embedding 3-ary n-cubes into certain cylinders and trees, Fundamenta Informaticae, 188 (2022), 269–284.
• [15] 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, 35 (2024), 409–434.
• [16] P. Manuel, I. Rajasingh, B. Rajan, and H. Mercy, Exact wirelength of hypercube on a grid, Discrete Applied Mathematics, 157 (2009), 1486-1495.
• [17] G.C. Vincy, and M.D. Raj, Minimum linear arrangement and embedding of (K¹¹ − C11) n into specific graphs with optimal wirelength calculation, The Journal of Supercomputing, 81 (2025).
• [18] P. Immanuel, and A.B. Greeni, Optimization of layout for embedding half hypercube into conventional tree architectures, Concurrency and Computation: Practice and Experience, 36 (2024).
• [19] 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, 35 (2024), 327-352.
• [20] P. Immanuel, and A.B. Greeni, Optimizing the layout of embedding BCube into grid architectures, Journal of Parallel and Distributed Computing, 201 (2025), 105070.

• [21] 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.
• [22] 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.
• [23] R.S. Rajan, R. Dominic, and N. Sadagopan, Optimal layout of (K^p − Cp) n into wheel like networks, Journal of Interconnection Networks, 25 (2025), 2450007.
• [24] 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, 24 (2024), 2350031.
• [25] 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, 27 (2023), 767–782.
• [26] 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, 79 (2023), 11300–11327.
• [27] P.L. Joshwa, R.S. Rajan, T.M. Rajalaxmi, I.N. Gangul, Embedding of extended sierpinski networks S ++(k, m) into certain trees, RAIRO-Operations Research, (2025), doi:10.1051/ro/2025085.
• [28] 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.
• [29] 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, (2024), 65–72, doi.org/10.1007/978-3-031-77764-6 8.
• [30] R.S. Rajan, P. Manuel and I. Rajasingh, Embeddings between Hypercubes and Hypertrees, Journal of Graph Algorithms and Applications, 19 (2015), 361-373.
• [31] P.L. Joshwa, R.S. Rajan, T.M. Rajalaxmi, Maximum subgraph and wirelength optimization in cyclic bipartite networks Gk,3, International Journal of Parallel, Emergent and Distributed Systems, (2026), 1-21. doi.org/10.1080/17445760.2025.2610814.
• [32] P.L. Joshwa, R.S. Rajan, T.M. Rajalaxmi, Maximum subgraph and wirelength analysis of extended Sierpinski networks in parallel computing, Discrete Applied Mathematics, ´ 383 (2026), 367-382.

• [33] 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, 64 (2010), 683-698.
• [34] 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, 2 (2017), 83–92.