On the Sombor Index of Sierpiński and Mycielskian Graphs

Document Type : Original paper

Authors

Amrita Vishwa Vidyapeetham, Coimbatore

Abstract

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)\).

Keywords

Main Subjects

References

[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.
http://dx.doi.org/10.12732/ijpam.v112i2.2
[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.
https://doi.org/10.11575/cdm.v15i3.68174
[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.
https://doi.org/10.1007/978–3–030–77983–2–5
[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.
https://doi.org/10.1016/j.amc.2021.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.
https://doi.org/10.3390/sym13010140
[10] K.C. Das, S. Das, and B. Zhou, Sum-connectivity index of a graph, Frontiers of Mathematics in China 11 (2016), 47–54.
https://doi.org/10.1007/s11464–015–0470–2
[11] K.C. Das and Y. Shang, Some extremal graphs with respect to Sombor index, Mathematics 9 (2021), no. 11, Article ID: 1202.
https://doi.org/10.3390/math9111202
[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.
https://doi.org/10.1016/j.dam.2021.01.018
[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.
https://doi.org/10.1016/j.dam.2018.03.032
[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.
https://doi.org/10.1142/S1793830921500191
[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.
https://doi.org/10.5562/cca2294
[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.
https://dx.doi.org/10.22049/cco.2022.27600.1296
[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.
https://doi.org/10.1016/j.dam.2016.09.024
[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.
https://doi.org/10.1016/j.chaos.2017.03.036
[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.
https://doi.org/10.1186/s13660–019–1990–1
[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.
https://doi.org/10.3233/JIFS–223326
[27] C. Phanjoubam and S. Mawiong, On Sombor index and some topological indices, Iranian J. Math. Chem. 12 (2021), no. 4, 209–215.
https://doi.org/10.22052/ijmc.2021.243137.1588
[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.
https://doi.org/10.20894/IJCOA.101.002.001.019
[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.
https://dx.doi.org/10.22049/cco.2021.27484.1272
[30] I. Redžepović, Chemical applicability of Sombor indices: Survey, J. Serbian Chem. Soc. 86 (2021), no. 5, 445–457.
https://doi.org/10.2298/JSC201215006R
[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.
https://doi.org/10.7151/dmgt.1945
[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.
https://doi.org/10.1515/math–2016–0055
[33] Y. Shang, Sombor index and degree-related properties of simplicial networks, Appl. Math. Comput. 419 (2022), Article ID: 126881.
https://doi.org/10.1016/j.amc.2021.126881
[34] M. Stiebitz, Beiträge zur theorie der färbungskritischen graphen, Ph.D. thesis, Technical University Ilmenau, 1985.
 
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 20 August 2023

Files

Share

How to cite

Statistics