An Upper Bound for Edge Congestion and the Exact Wirelength of Embedding onto BC Graphs
R. Sundara Rajan, Remi Mariam Reji, T. M. Rajalaxmi · International Journal of Foundations of Computer Science · 2025
Graph embedding refers to the process of mapping a guest graph A into a host graph B. It is a frequently employed method in interconnection networks to evaluate the computational capabilities of these networks. It serves as a robust instrument for simulating diverse interconnection networks or executing parallel algorithms. One of the cost criteria in measuring the quality of an embedding is edge congestion. In this research, we calculate an upper limit for the edge congestion when embedding any graph, and we additionally create a host graph where this limit is attained. Another cost criterion in measuring the quality of an embedding is wirelength. The bijective connection graphs (for short, BC graphs) are cube-like graphs consisting of most of the variants of cube structures such as hypercube [Formula: see text], twisted cube [Formula: see text], twisted n-cube [Formula: see text], locally twisted cube [Formula: see text], generalized twisted cube [Formula: see text], multiply-twisted cube [Formula: see text], crossed cube [Formula: see text], shuffle cube [Formula: see text], Möbius cube [Formula: see text], spined cube [Formula: see text], Z-cube [Formula: see text], etc. In the literature, the wirelength of embedding the variants in BC graphs into various host graphs has been studied separately by many authors. An important question arising about the wirelength of embedding is: Does the BC graphs (including all hypercube variants) are considered as a guest graph and its wirelength is obtained for any host graph? To answer this question, only in 2018, Jiang et al. (Discrete Mathematics, Algorithms and Applications, 10(2), 2018) calculated the wirelength of embedding BC graphs into a path and produced the exact value. In this paper, we highlight the fact that, if any one of the families in the BC graphs belonging to [Formula: see text] can be embedded into any host graph H that admits a convex edge partition with a minimum wirelength, then the remaining family in BC graphs belonging to P will be embedded into the host graph H and produce the same wirelength.