Embedding of extended sierpinski networks S⁺⁺(k, m) into certain trees

¹ Department of Mathematics, Hindustan Institute of Technology and Science, Chennai 603103, India
² Department of Mathematics, Sri Sivasubramaniya Nadar College of Engineering, Chennai 603110, India
³ Department of Mathematics, Bursa Uludag University, Gorukle-Bursa 16059, Turkey

^* Corresponding author: vprsundar@gmail.com

Received: 27 December 2024
Accepted: 20 June 2025

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.