Maximum subgraph and wirelength analysis of extended Sierpiński graph S+(n, K3)

Joshwa, P. Leo; Rajan, R. Sundara; Emilet, D. Ahima; Arulanand, S.

doi:10.47974/JDMSC-2577

Open Access Research Article

Maximum subgraph and wirelength analysis of extended Sierpiński graph S+(n, K3)

P. Leo Joshwajoseleowa18@gmail.comDepartment of Mathematics Hindustan Institute of Technology & ScienceChennai, Tamil Nadu, 603103, India0000-0002-0365-2309View full profile → , ^*R. Sundara RajanCorresponding authorvprsundar@gmail.comDepartment of Mathematics Rajalakshmi Engineering CollegeChennai, Tamil Nadu, 602105, India0000-0002-1851-6334View full profile → , D. Ahima Emiletahi.180492@gmail.comDepartment of Mathematics Hindustan Institute of Technology & ScienceChennai, Tamil Nadu, 603103, India0000-0002-3424-2126View full profile → , S. Arulanandarulanand7875@gmail.comDepartment of Mathematics Rajalakshmi Institute of TechnologyChennai, Tamil Nadu, 600124, India0000-0001-9862-0213View full profile →

* Corresponding author · click or hover a name for details

pp. 2321–2332Vol. 29Issue 6June 2026DOI: 10.47974/JDMSC-2577 Crossmark XML

Received:: 01 May 2025
Published Online:: 20 Jun 2026
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-2577
Pages:: 2321–2332

Abstract

The Sierpiński graph S(n, Km), known for its recursive and hierarchical construction, serves as a significant model for multiprocessor interconnection architectures. Its extended variant, denoted S+ (n, Km), further strengthens these properties and has practical relevance in areas such as parallel computation and VLSI circuit design. This work investigates the unresolved Maximum Subgraph Problem (MSP) for the extended Sierpiński graph S+ (n, Km), with n ≥ 2, a problem originally proposed by Joshwa et al. [1], and still open for general values of m. We introduce a computational framework, implemented in SageMath, for determining the maximal edge count among all subgraphs induced by r vertices, where 1 ≤ r ≤ 3n + 1. In addition, we examine minimum wirelength embeddings of S+ (n, Km) into various hierarchical graph topologies, a key factor in optimizing communication efficiency and layout complexity in networked systems.

Keywords

Embedding Wirelength Extended Sierpiński graph S+(n K3)Maximum subgraph Hierarchical structures

Subject Classifications

05C1005C6005C6205C75

References

[1] P. L. Joshwa, R. S. Rajan, T. M. Rajalaxmi, and I. N. Cangul, “Embedding of extended Sierpiński network S++ (k,m) into certain trees,” RAIRO Operations Research, vol. 59, no. 4, pp. 2279-2301 (2025).
[2] S. L. Bezrukov, J. D. Chavez, L. H. Harper, M. Rotteger, and U. P. Schroeder, “Embedding of hypercube into grids,” in Mathematical Foundations of Computer Science, vol. 1450, pp. 693-701 (1998).
[3] P. Manuel, I. Rajasingh, B. Rajan, and H. Mercy, “Exact wirelength of hypercubes on a grid,” Discrete Applied Mathematics, vol. 157, no. 7, pp. 1486-1495 (2009).
[4] S. L. Bezrukov, “Edge isoperimetric problems on graphs,” Graph Theory and Combinatorial Biology, vol. 7, pp. 157-197 (1999).
[5] S. Klavžar and U. Milutinović, “Graphs S(n,k) and a variant of the Tower of Hanoi problem,” Czechoslovak Mathematical Journal, vol. 47, no. 1, pp. 95-104 (1997).
[6] R. S. Rajan, A. B. Greeni, and P. L. Joshwa, “Maximum subgraph problem and minimum linear arrangement of generalized Sierpiński graphs,” Journal of Graph Algorithms and Applications, vol. 27, no. 9, pp. 767-782 (2023).
[7] L. H. Harper, “The edge-isoperimetric problem on Sierpiński graph: Final resolution,” arXiv preprint arXiv:1802.08355 (2018).
[8] P. L. Joshwa, R. S. Rajan, and T. M. Rajalaxmi, “Maximum subgraph and wirelength optimization in cyclic bipartite networks Gk,3,” Int. J. Parallel, Emergent Distrib. Syst., pp. 1–21 (Jan. 2026), doi: 10.1080/17445760.2025.2610814.
[9] P. L. Joshwa, R. S. Rajan, and T. M. Rajalaxmi, “Maximum subgraph and wirelength analysis of extended Sierpiński networks in parallel computing,” Discrete Applied Mathematics, vol. 383, pp. 367-382 (2026).
[10] G. K. Nandini, S. Klavžar, T. M. Rajalaxmi, and R. S. Rajan, “A note on eccentricity based topological indices of honeycomb, oxide and 2-power interconnection networks,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 26, no. 1, pp. 231-253 (2023).
[11] S. Arulanand, R. S. Rajan, S. Prabhu, and S. Stephen, “Certain domination numbers for Cartesian product of graphs,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 27, no. 3, pp. 1045-1058 (2024).
[12] A. Khobragade, R. Mahajan, H. Langi, R. Mundhe, and S. Ghumbre, “Effective negative triplet sampling for knowledge graph embedding,” Journal of Information and Optimization Sciences, vol. 43, no. 8, pp. 2075-2087 (2022).
[13] G. M. Jose, K. N. Geetha, and K. Somasundaram, “Double power domination in graphs,” Journal of Discrete Mathematical Sciences and Cryptography, vol. 28, no. 6, pp. 2261-2278 (2025).
[14] S. Klavzar and B. Mohar, “Crossing numbers of Sierpiński-like graphs,” Journal of Graph Theory, Vol. 50, no. 3, pp. 186–198 (2005).
[15] L. H. Harper, “Optimal assignments of numbers to vertices,” Journal of the Society for Industrial and Applied Mathematics, Vol. 12, no. 1, pp. 131–135 (1964).

Views: 54Downloads: 16Citations: 0