On the Sombor Index of Sierpiński and Mycielskian Graphs

Document Type : Original paper


Amrita Vishwa Vidyapeetham, Coimbatore


In 2020, mathematical chemist, Ivan Gutman, introduced a new vertex-degree-based topological index called the Sombor Index, denoted by $SO(G)$, where $G$ is a simple, connected, finite, graph. This paper aims to present some novel formulas, along with some upper and lower bounds on the Sombor Index of generalized Sierpi'nski graphs; originally defined by Klav\v{z}ar and Milutinovi'c by replacing the complete graph appearing in $S(n,k)$ with any graph and exactly replicating the same graph, yielding self-similar graphs of fractal nature; and on the Sombor Index of the $m$-Mycielskian or the generalized Mycielski graph; formed from an interesting construction given by Jan Mycielski (1955); of some simple graphs such as \(K_n\), \(C_n^2\), \(C_n\), and \(P_n\). We also provide Python codes to verify the results for the \(SO\left(S\left(n,K_m\right)\right)\) and \(SO\left(\mu_m\left(K_n\right)\right)\).


Main Subjects

[1] V. Anandkumar and R.R. Iyer, On the hyper-Zagreb index of some operations on graphs, Int. J. Pure Appl. Math. 112 (2017), 239–252.
[2] A. Behtoei and M. Anbarloei, Gutman index of the Mycielskian and its complement, arXiv:1502.01580 (2015).
[3] A. Behtoei, M. Khatibi, and F. Attarzadeh, Degree sequence of the generalized sierpiński graph, 2020, pp. 88–97.
[4] D. Boutin, S. Cockburn, L. Keough, S. Loeb, K.E. Perry, and P. Rombach, Symmetry parameters for Mycielskian graphs, pp. 99–117. Springer International Publishing, Cham, 2021.
[5] V. Chvátal, The minimality of the Mycielski graph, Graphs and Combinatorics (Berlin, Heidelberg) (R.A. Bari and F. Harary, eds.), Springer Berlin Heidelberg, 1974, pp. 243–246.
[6] M.T. Cronin, J. Leszczynski, and T. Puzyn, Recent Advances in QSAR Studies Methods and Applications, Challenges and Advances in Computational Chemistry and Physics, vol. 8, Springer, Dordrecht, Heidelberg, London, New York, 2010.
[7] R. Cruz, I. Gutman, and J. Rada, Sombor index of chemical graphs, Appl. Math. Comput. 399 (2021), Article ID: 126018.
[8] R. Cruz, A. Santamaría-Galvis, and J. Rada, Extremal values of vertex-degree-based topological indices of coronoid systems, Int. J. Quantum Chem. 121 (2020), no. 6, https://doi.org/10.1002/qua.26536.
[9] K.C. Das, A.S. Çevik, I.N. Cangul, and Y. Shang, On Sombor index, Symmetry 13 (2021), no. 1, Article number: 140.
[10] K.C. Das, S. Das, and B. Zhou, Sum-connectivity index of a graph, Frontiers of Mathematics in China 11 (2016), 47–54.
[11] K.C. Das and Y. Shang, Some extremal graphs with respect to Sombor index, Mathematics 9 (2021), no. 11, Article ID: 1202.
[12] Kinkar Chandra Das, Suresh Elumalai, and Selvaraj Balachandran, Open problems on the exponential vertex-degree-based topological indices of graphs, Discrete Appl. Math. 293 (2021), 38–49.
[13] J. Devillers and A.T. Balaban (eds.), Topological Indices and Related Descriptors in QSAR and QSPR, CRC Press, London, 1999.
[14] A. Estrada-Moreno and J.A. Rodríguez-Velázquez, On the general Randić index of polymeric networks modelled by generalized Sierpi´nski graphs, Discrete Appl. Math. 263 (2019), 140–151.
[15] C. Gopika, J. Geetha, and K. Somasundaram, Weighted PI index of tensor product and strong product of graphs, Discrete Math. Algorithms Appl. 13 (2021), Atricle ID: 2150019.
[16] S. Gravier, M. Kovse, and A. Parreau, Generalized sierpiński graphs 1, Posters at EuroComb’11, Rényi Institute, Budapest, 2011.
[17] I. Gutman, Degree-based topological indices, Croatica Chemica Acta 86 (2013), no. 4, 351–361.
[18] I. Gutman, Geometric approach to degree–based topological indices: Sombor indices, MATCH Commun. Math. Comput. Chem. 86 (2021), no. 1, 11–16.
[19] I. Gutman, N. Gürsoy, A. Gürsoy, and A. Ülker, New bounds on Sombor index, Commun. Comb. Optim. 8 (2023), no. 2, 305–311.
[20] Toru Hasunuma, Structural properties of subdivided-line graphs, J. Discrete Algorithms 31 (2015), 69–86, 24th International Workshop on Combinatorial Algorithms (IWOCA 2013).
[21] A.M. Hinz, S. Klavžar, and S.S. Zemljič, A survey and classification of sierpiński type graphs, Discrete Appl. Math. 217 (2017), 565–600.
[22] M. Imran, S. Hafi, W. Gao, and M.R. Farahani, On topological properties of sierpiński networks, Chaos, Solitons & Fractals 98 (2017), 199–204.
[23] I. Javaid, H. Benish, M. Imran, A. Khan, and Z. Ullah, On some bounds of the topological indices of generalized Sierpński and extended Sierpiński graphs, J. Ine. Appl. 2019 (2019), Article number: 37.
[24] I. Milovanović, E. Milovanović, A. Ali, and M. Matejić, Some results on the Sombor indices of graphs, Contrib. Math. 3 (2021), 59–67. https://doi.org/10.47443/cm.2021.0024.
[25] J. Mycielski, Sur le coloriage des graphs, Colloquium Math. 3 (1955), no. 2, 161–162 (Fre).
[26] P.G. Nayana and R.R. Iyer, On secure domination number of generalized Mycielskian of some graphs, J. Intelligent & Fuzzy Sys 44 (2023), no. 3, 4831–4841.
[27] C. Phanjoubam and S. Mawiong, On Sombor index and some topological indices, Iranian J. Math. Chem. 12 (2021), no. 4, 209–215.
[28] S. Ramakrishnan, J. Senbagamalar, and J. Baskar Babujee, Topological indices of molecular graphs under specific chemical reactions, Int. J. Comput. Algorithm 2 (2013), 68–74.
[29] H. Ramane, I. Gutman, K. Bhajantri, and D. Kitturmath, Sombor index of some graph transformations, Commun. Comb. Optim. 8 (2023), no. 1, 193–205.
[30] I. Redžepović, Chemical applicability of Sombor indices: Survey, J. Serbian Chem. Soc. 86 (2021), no. 5, 445–457.
[31] J.A. Rodríguez-Velázquez, E.D. Rodríguez-Bazan, and A. Estrada-Moreno, On generalized Sierpiński graphs, Discuss. Math. Graph Theory 37 (2017), no. 3, 547–560.
[32] Y. Shang, On the number of spanning trees, the laplacian eigenvalues, and the laplacian estrada index of subdivided-line graphs, Open Math. 14 (2016), no. 1, 641–648.
[33] Y. Shang, Sombor index and degree-related properties of simplicial networks, Appl. Math. Comput. 419 (2022), Article ID: 126881.
[34] M. Stiebitz, Beiträge zur theorie der färbungskritischen graphen, Ph.D. thesis, Technical University Ilmenau, 1985.