The extremal Sombor index of trees with a given dissociation number $\varphi$

Articles in Press

Document Type : Original paper

Author

Department of Mathematics, College of Engineering and Technology SRM Institute of Science and Technology, Kattankulathur, Chennai 603203, India

Abstract

The Sombor index is a topological index in graph theory defined by Gutman in 2021. In this article, we find the maximum Sombor index of trees of order $\mathbf{n}$ with a given dissociation number $\varphi$, where $\ceil*{\frac{2\mathbf{n}}{3}} \leq \varphi(G) \leq \mathbf{n}-1$. We also provide the unique graph among the chosen class where the maximum Sombor index is attained.

Keywords

Main Subjects

References

[1] S. Alikhani and N. Ghanbari, Sombor index of polymers, MATCH Commun. Math. Comput. Chem. 86 (2021), no. 3, 715–728.
[2] B. Borovi´canin, B. Furtula, and M. Jerotijevi´c, On the minimum Harary index of graphs with a given diameter or independence number, Discrete Appl. Math. 320 (2022), 331–345. https://doi.org/10.1016/j.dam.2022.06.008
[3] B. Brešar, M. Jakovac, J. Katrenič, G. Semanišin, and A. Taranenko, On the vertex $k$-path cover, Discrete Appl. Math. 161 (2013), no. 13-14, 1943–1949. https://doi.org/10.1016/j.dam.2013.02.024
[4] B. Brešar, F. Kardoš, J. Katrenič, and G. Semanišin, Minimum $k$-path vertex cover, Discrete Appl. Math. 159 (2011), no. 12, 1189–1195. https://doi.org/10.1016/j.dam.2011.04.008
[5] R. Cruz, I. Gutman, and J. Rada, Sombor index of chemical graphs, Appl. Math. Comput. 399 (2021), 126018.
https://doi.org/10.1016/j.amc.2021.126018
[6] J. Das, On extremal Sombor index of trees with a given independence number $\alpha$, Discrete Math. Algorithms Appl. (2026), 2650057. https://doi.org/10.1142/S1793830926500576
[7] J. Das and S. Mohanty, Maximization of the spectral radius of block graphs with a given dissociation number, Appl. Math. Comput. 465 (2024), 128424. https://doi.org/10.1016/j.amc.2023.128424
[8] J. Das and Y. Prajapaty, On Sombor index of unicyclic graphs with a fixed number of pendant vertices, 2022. https://doi.org/10.48550/arXiv.2212.07732
[9] K.C. Das and Y. Shang, Some extremal graphs with respect to Sombor index, Mathematics 9 (2021), no. 11, 1202.
https://doi.org/10.3390/math9111202
[10] K.C. Das, A.S. Çevik, I.N. Cangul, and Y. Shang, On Sombor index, Symmetry 13 (2021), no. 1, 140. https://doi.org/10.3390/sym13010140
[11] S. Filipovski, Relations between Sombor index and some degree-based topological indices, Iranian J. Math. Chem. 12 (2021), no. 1, 19–26. https://doi.org/10.22052/ijmc.2021.240385.1533
[12] I. Gutman, Geometric approach to degree-based topological indices: Sombor indices, MATCH Commun. Math. Comput. Chem. 86 (2021), no. 1, 11–16.
[13] , Some basic properties of Sombor indices, Open J. Discrete Appl. Math. 4 (2021), no. 1, 1–3. https://doi.org/10.30538/psrp–odam2021.0047
[14] B. Horoldagva and C. Xu, On Sombor index of graphs, MATCH Commun. Math. Comput. Chem. 86 (2021), no. 3, 703–713.
[15] J. Huang, X. Geng, S. Li, and Z. Zhou, On spectral extrema of graphs with given order and dissociation number, Discrete Appl. Math. 342 (2024), 368–380. https://doi.org/10.1016/j.dam.2023.10.001
[16] Y. Orlovich, A. Dolgui, G. Finke, V. Gordon, and F. Werner, The complexity of dissociation set problems in graphs, Discrete Appl. Math. 159 (2011), no. 13, 1352–1366. https://doi.org/10.1016/j.dam.2011.04.023
[17] I. Redžepović, Chemical applicability of Sombor indices, Serb. Chem. Soc. 86 (2021), no. 5, 445–457. https://doi.org/10.2298/JSC201215006R
[18] T. Réti, T. Došlić, and A. Ali, On the Sombor index of graphs, Contrib. Math. 3 (2021), 11–18. https://doi.org/10.47443/cm.2021.0006
[19] X. Sun and J. Du, On Sombor index of trees with fixed domination number, Appl. Math. Comput. 421 (2022), 126946.
https://doi.org/10.1016/j.amc.2022.126946
[20] I. Tomescu, Extremal vertex-degree function index for trees and unicyclic graphs with given independence number, Discrete Appl. Math. 306 (2022), 83–88. https://doi.org/10.1016/j.dam.2021.09.028
[21] J. Tu, Y. Li, and J. Du, Maximal and maximum dissociation sets in general and triangle-free graphs, Appl. Math. Comput. 426 (2022), 127107. https://doi.org/10.1016/j.amc.2022.127107
[22] J. Tu, Z. Zhang, and Y. Shi, The maximum number of maximum dissociation sets in trees, J. Graph Theory 96 (2021), no. 4, 472–489. https://doi.org/10.1002/jgt.22627
[23] A. Vasilyev, R. Darda, and D. Stevanović, Trees of given order and independence number with minimal first Zagreb index, MATCH Commun. Math. Comput. Chem. 72 (2014), no. 3, 775–782.
[24] Z. Wang, Y. Mao, Y. Li, and B. Furtula, On relations between Sombor and other degree-based indices, J. Appl. Math. Comput. 68 (2022), 1–17. https://doi.org/10.1007/s12190-021-01516-x
[25] T. Zhou, Z. Lin, and L. Miao, The Sombor index of trees and unicyclic graphs with given maximum degree, Discrete Math. Lett. 7 (2021), 24–29. https://doi.org/10.47443/dml.2021.0035
[26] , The extremal sombor index of trees and unicyclic graphs with given matching number, Journal of Discrete Mathematical Sciences and Cryptography 26 (2022), no. 1, 1–12. https://doi.org/10.1080/09720529.2021.2015090
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 05 July 2026

Files

Share

How to cite

Statistics