Answers are grounded in this paper and cite their sources.
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.
No takes yet. Share an insight, caveat, or question.
Joshwa et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: