{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T21:21:42Z","timestamp":1771104102230,"version":"3.50.1"},"reference-count":32,"publisher":"EDP Sciences","issue":"4","license":[{"start":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T00:00:00Z","timestamp":1757030400000},"content-version":"vor","delay-in-days":66,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Anusandhan National Research Foundation (ANRF), Science and Engineering Research Board (SERB), Government of India for funding under the Teachers Associateship for Research Excellence","award":["TAR\/2023\/000041"],"award-info":[{"award-number":["TAR\/2023\/000041"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2025,6,20]]},"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:p>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 <jats:italic>S<\/jats:italic><jats:sup>++<\/jats:sup>(<jats:italic>k, m<\/jats:italic>), a hierarchical structure with wide applicability. For <jats:italic>k<\/jats:italic> \u2265 2 and <jats:italic>m<\/jats:italic> = 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 <jats:italic>m<\/jats:italic> in <jats:italic>S<\/jats:italic><jats:sup>++<\/jats:sup>(<jats:italic>k, m<\/jats:italic>) remains an open problem. This work extends prior findings on generalized Sierpinski networks, offering new insights into their structural properties and optimization.<\/jats:p>","DOI":"10.1051\/ro\/2025085","type":"journal-article","created":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T07:45:55Z","timestamp":1750664755000},"page":"2279-2301","source":"Crossref","is-referenced-by-count":3,"title":["Embedding of extended sierpinski networks <i>S<\/i><sup>++<\/sup>(<i>k, m<\/i>) into certain trees"],"prefix":"10.1051","volume":"59","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0365-2309","authenticated-orcid":false,"given":"P. Leo","family":"Joshwa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1851-6334","authenticated-orcid":false,"given":"Sundara","family":"Rajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9700-8110","authenticated-orcid":false,"given":"T.M.","family":"Rajalaxmi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0700-5774","authenticated-orcid":false,"given":"Ismail Naci","family":"Cangul","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2025,9,5]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1016\/j.ipl.2011.06.011","volume":"111","author":"Arockiaraj","year":"2011","journal-title":"Inf. Process. Lett."},{"key":"R2","first-page":"187","volume":"178","author":"Arockiaraj","year":"2021","journal-title":"Fund. Inf."},{"key":"R3","first-page":"157","volume":"7","author":"Bezrukov","year":"1999","journal-title":"Bolyai Soc. Math. Stud."},{"key":"R4","first-page":"693","volume":"1450","author":"Bezrukov","year":"1998","journal-title":"Math. Found. Comput. Sci."},{"key":"R5","first-page":"337","volume":"21","author":"Chen","year":"1997","journal-title":"Southeast Asian Bull. Math."},{"key":"R6","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s12190-008-0155-z","volume":"30","author":"Choudum","year":"2009","journal-title":"J. Appl. Math. Comput."},{"key":"R7","first-page":"3","volume":"15","author":"Fan","year":"2018","journal-title":"International Conference on Algorithms and Architectures for Parallel Processing"},{"key":"R8","unstructured":"Garey M.R. and Johnson D.S., Computers and Intractability: a guide to the theory of NP-Completeness. Freeman, San Francisco, California (1979)."},{"key":"R9","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1137\/0112012","volume":"12","author":"Harper","year":"1964","journal-title":"Soc. Ind. Appl. Math."},{"key":"R10","unstructured":"Harper L., Global Methods for Combinatorial Isoperimetric Problems. Vol. 90. Cambridge University Press (2006)."},{"key":"R11","unstructured":"Harper L.H., Can the Sierpinski graph be embedded in the Hamming graph? Preprint arXiv:1609.06777 (2016)."},{"key":"R12","unstructured":"Harper L., The edge-isoperimetric problem on sierpinski graph: final resolution. Preprint arXiv:1802.08355 (2018)."},{"key":"R13","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1016\/j.dam.2016.09.024","volume":"217","author":"Hinz","year":"2017","journal-title":"Discrete Appl. Math."},{"key":"R14","doi-asserted-by":"crossref","first-page":"513","DOI":"10.11650\/twjm\/1500574171","volume":"12","author":"Klav\u017ear","year":"2008","journal-title":"Taiwanese J. Math."},{"key":"R15","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1023\/A:1022444205860","volume":"47","author":"Klav\u017ear","year":"1997","journal-title":"Czechoslovak Math. J."},{"key":"R16","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1002\/jgt.20107","volume":"50","author":"Klav\u017ear","year":"2005","journal-title":"J. Graph Theory"},{"key":"R17","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1016\/j.dam.2008.09.013","volume":"157","author":"Manuel","year":"2009","journal-title":"Discrete Appl. Math."},{"key":"R18","doi-asserted-by":"crossref","first-page":"2109","DOI":"10.1016\/j.dam.2011.07.003","volume":"159","author":"Manuel","year":"2011","journal-title":"Discrete Appl. Math."},{"key":"R19","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1504\/IJNVO.2017.083547","volume":"17","author":"Parthiban","year":"2017","journal-title":"Int. J. Netw. Virtual Org."},{"key":"R20","doi-asserted-by":"crossref","first-page":"3271","DOI":"10.1093\/comjnl\/bxv021","volume":"58","author":"Rajan","year":"2015","journal-title":"Comput. J."},{"key":"R21","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1093\/comjnl\/bxu031","volume":"58","author":"Rajan","year":"2015","journal-title":"Comput. J."},{"key":"R22","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/j.dam.2018.05.034","volume":"280","author":"Rajan","year":"2020","journal-title":"Discrete Appl. Math."},{"key":"R23","doi-asserted-by":"crossref","first-page":"767","DOI":"10.7155\/jgaa.00644","volume":"27","author":"Rajan","year":"2023","journal-title":"J. Graph Algorithms App."},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Rajan R., Reji R. and Rajalaxmi T., Maximum subgraph problem for 3-regular Kn\u00f6del graphs and its wirelength, in Conference on Algorithms and Discrete Applied Mathematics (2023) 403\u2013414.","DOI":"10.1007\/978-3-031-25211-2_31"},{"key":"R25","first-page":"2450007","volume":"27","author":"Rajan","year":"2024","journal-title":"J. Interconnection Netw."},{"key":"R26","doi-asserted-by":"crossref","first-page":"2450008","DOI":"10.1142\/S0129626424500087","volume":"34","author":"Rajan","year":"2024","journal-title":"Parallel Process. Lett."},{"key":"R27","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/s11786-011-0085-2","volume":"5","author":"Rajasingh","year":"2011","journal-title":"Math. Comput. Sci."},{"key":"R28","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/s10878-011-9443-x","volume":"26","author":"Rajasingh","year":"2013","journal-title":"J. Comb. Optim."},{"key":"R29","doi-asserted-by":"crossref","first-page":"1550008","DOI":"10.1142\/S0129626415500085","volume":"25","author":"Rajasingh","year":"2015","journal-title":"Parallel Process. Lett."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"Rajeshwari S. and Rajesh M., Exact wirelength of embedding 3-ary n-cubes into certain cylinders and trees. Fund. Inf. 188 (2023).","DOI":"10.3233\/FI-222149"},{"key":"R31","doi-asserted-by":"crossref","first-page":"2350031","DOI":"10.1142\/S0219265923500317","volume":"24","author":"Reji","year":"2024","journal-title":"J. Interconnection Netw."},{"key":"R32","unstructured":"Xu J., Topological Structure and Analysis of Interconnection Networks. Vol. 7. Springer Science & Business Media (2013)."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2025085\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T07:57:53Z","timestamp":1757059073000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2025085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":32,"journal-issue":{"issue":"4"},"alternative-id":["ro240856"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2025085","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"2804-7303","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7]]}}}