Optimizing Maximum Subgraph and Wirelength in WK-Recursive Networks

The Sierpiński network [Formula: see text] has become a prominent model for multiprocessor interconnection systems. Among hierarchical interconnection structures, the WK-recursive networks [Formula: see text] are notable for their advantageous properties, making them highly suitable for applications in parallel computing and VLSI design. These networks exhibit desirable features such as small diameter, high connectivity, and strong scalability. In this paper, we focus on solving the NP-complete Maximum Subgraph Problem (MSP) within the WK-recursive framework [Formula: see text], where [Formula: see text] and [Formula: see text]. We propose a computational method based on lexicographic ordering, implemented in SageMath, to determine the maximum number of edges that can be induced by any subset of [Formula: see text] vertices, for [Formula: see text]. Furthermore, we explore the Minimum Linear Arrangement (MinLA) problem by investigating embeddings of WK-recursive networks into host structures specifically path graphs, caterpillars, 1-hierarchical caterpillars, windmill, and necklace graph that aim to minimize total wirelength.