Embedding of extended sierpinski networks <i>S</i><SUP>++</SUP>(<i>k, m</i>) into certain trees
RAIRO-OPERATIONS RESEARCH, vol.59, no.4, pp.2279-2301, 2025 (SCI-Expanded, Scopus)
- Publication Type: Article / Article
- Volume: 59 Issue: 4
- Publication Date: 2025
- Doi Number: 10.1051/ro/2025085
- Journal Name: RAIRO-OPERATIONS RESEARCH
- Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, ABI/INFORM, Aerospace Database, Business Source Elite, Business Source Premier, Communication Abstracts, Metadex, zbMATH, Civil Engineering Abstracts
- Page Numbers: pp.2279-2301
- Bursa Uludag University Affiliated: Yes
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.