Embedding of extended sierpinski networks <i>S</i><SUP>++</SUP>(<i>k, m</i>) into certain trees

Joshwa P. L., Rajan S., Rajalaxmi T. M., CANGÜL İ. N.

RAIRO-OPERATIONS RESEARCH, cilt.59, sa.4, ss.2279-2301, 2025 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 59 Sayı: 4
  • Basım Tarihi: 2025
  • Doi Numarası: 10.1051/ro/2025085
  • Dergi Adı: RAIRO-OPERATIONS RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, ABI/INFORM, Aerospace Database, Business Source Elite, Business Source Premier, Communication Abstracts, Metadex, zbMATH, Civil Engineering Abstracts
  • Sayfa Sayıları: ss.2279-2301
  • Bursa Uludağ Üniversitesi Adresli: Evet

Özet

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.