Embedding of extended Sierpinski networks S++(k, m) into certain trees

Abstract

The Maximum Subgraph Problem (MSP) seeks to maximize the edges induced by a subset of vertices in a graph, a challenge that is NP-complete and fundamental to applications in parallel computing and VLSI design. In this paper, we study the MSP for the extended Sierpinski networks S⁺⁺(K, M), a hierarchical structure with wide applicability. For K ≥ 2 and M = 3, 4, we leverage lexicographic ordering to determine the maximum number of edges for given vertex subsets and provide a Sage implementation for computation. Further, we explore the minimum wirelength required for embedding the extended Sierpinski networks into structures such as the minimum linear arrangement, complete binary tree, caterpillar, and 1-hierarchical caterpillar. While our results address specific cases, the MSP for arbitrary M in S⁺⁺(K, M) remains an open problem. This work extends prior findings on generalized Sierpinski networks, offering new insights into their structural properties and optimization.