On extremal trees for the minimum Sombor index with fixed total domination number

Articles in Press

Document Type : Original paper

Authors

1 Department of Economy, Quantitative Methods and Economic History, Pablo de Olavide University, Carretera de Utrera Km. 1, 41013-Sevilla, Spain

2 Facultad de Ciencias Agrarias, Universidad Nacional del Nordeste, Juan Bautista Cabral 2131, Corrientes, Argentina

3 Department of Mathematics, Faculty of Sciences, Golestan University, Gorgan, Iran

Abstract

The Sombor index of a graph $G$ is a degree-based graph structure descriptor, defined as $SO(G)=\sum_{uv \in E(G)}\sqrt{d(u)^2+d(v)^2},$ in which $d(x)$ is the degree of the vertex $x \in V(G)$, for $x=u, v$. In this paper, we find a sharp lower bound of the Sombor index in trees with fixed total domination number and we characterize the extremal trees. More precisely, given any tree $T$ with order $n$ and total domination number $\gamma_t$, we prove that
$SO(T)\geq \left(2\sqrt{13}+\sqrt{5}-\frac{7\sqrt{2}}{2}\right)(n-2\gamma_t)+4\sqrt{2}\gamma_t+2\sqrt{5}-6\sqrt{2}.$
This lower bound improves, in many cases, the known lower bounds given with the order and with the order and the domination number of the tree.

Highlights

á

Keywords

Main Subjects

References

[1] A.A.S. Ahmad Jamri, F. Movahedi, R. Hasni, and M.H. Akhbari, A lower bound for the second Zagreb index of trees with given Roman domination number, Commun. Comb. Optim. 8 (2023), no. 2, 391–396. https://doi.org/10.22049/cco.2022.27553.1288
[2] A.A.S. Ahmad Jamri, F. Movahedi, R. Hasni, R. Gobithaasan, and M.H. Akhbari, Minimum Randićindex of trees with fixed total domination number, Mathematics 10 (2022), no. 20, 3729. https://doi.org/10.3390/math10203729
[3] S. Bermudo, Upper bound for the geometric-arithmetic index of trees with given domination number, Discrete Math. 346 (2023), no. 1, 113172. https://doi.org/10.1016/j.disc.2022.113172
[4] S. Bermudo, R. Hasni, F. Movahedi, and J.E. Nápoles, The geometric–arithmetic index of trees with a given total domination number, Discrete Appl. Math. 345 (2024), 99–113. https://doi.org/10.1016/j.dam.2023.11.024
[5] S. Bermudo, J.E. Nápoles, and J. Rada, Extremal trees for the Randićindex with given domination number, Appl. Math. Comput. 375 (2020), 125122. https://doi.org/10.1016/j.amc.2020.125122.
[6] B. Borovićanin and B. Furtula, On extremal Zagreb indices of trees with given domination number, Appl. Math. Comput. 279 (2016), 208–218. https://doi.org/10.1016/j.amc.2016.01.017
[7] 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
[8] R. Cruz and J. Rada, Extremal values of the Sombor index in unicyclic and bicyclic graphs, J. Math. Chem. 59 (2021), no. 4, 1098–1116. https://doi.org/10.1007/s10910-021-01232-8
[9] 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
[10] K.C. Das and I. Gutman, On Sombor index of trees, Appl. Math. Comput. 412 (2022), 126575. https://doi.org/10.1016/j.amc.2021.126575
[11] H. Deng, Z. Tang, and R. Wu, Molecular trees with extremal values of Sombor indices, Int. J. Quantum Chem. 121 (2021), no. 11, e26622. https://doi.org/10.1002/qua.26622
[12] J. Devillers and A.T. Balaban, Topological Indices and Related Descriptors in QSAR and QSPR, CRC Press, 2000.
[13] 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
[14] I. Gutman, Geometric approach to degree-based topological indices: Sombor indices, MATCH Commun. Math. Comput. Chem 86 (2021), 11–16.
[15] M.A. Henning and A. Yeo, Total Domination in Graphs, Springer, 2013.
[16] S. Li, Z. Wang, and M. Zhang, On the extremal Sombor index of trees with a given diameter, Appl. Math. Comput. 416 (2022), 126731. https://doi.org/10.1016/j.amc.2021.126731
[17] V. Maitreyi, S. Elumalai, S. Balachandran, and H. Liu, The minimum Sombor index of trees with given number of pendant vertices, Comput. Appl. Math. 42 (2023), no. 8, 331. https://doi.org/10.1007/s40314-023-02479-4
[18] D.A. Mojdeh, M. Habibi, L. Badakhshian, and Y. Rao, Zagreb indices of trees, unicyclic and bicyclic graphs with given (total) domination, IEEE Access 7 (2019), 94143–94149. https://doi.org/10.1109/ACCESS.2019.2927288
[19] F. Movahedi, Extremal trees for Sombor index with given degree sequence, Iranian J. Math. Chem. 13 (2022), no. 4, 281–290. https://doi.org/10.22052/ijmc.2022.248570.1676
[20] F. Movahedi and M.H. Akhbari, Degree-based topological indices of the molecular structure of hyaluronic acid–methotrexate conjugates in cancer treatment, Int. J. Quantum Chem. 123 (2023), no. 12, e27106. https://doi.org/10.1002/qua.27106
[21] F. Movahedi and M.H. Akhbari, Entire Sombor index of graphs, Iranian J. Math. Chem. 14 (2023), no. 1, 33–45.
https://doi.org/10.22052/ijmc.2022.248350.1663
[22] M.R. Oboudi, On graphs with integer Sombor index, J. Appl. Math. Comput. 69 (2023), no. 1, 941–952. https://doi.org/10.1007/s12190-022-01778-z
[23] I. Redžepović, Chemical applicability of Sombor indices, J. Serb. Chem. Soc. 86 (2021), no. 5, 445–457. https://doi.org/10.2298/JSC201215006R
[24] 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
[25] A. Ülker, A. Gürsoy, and N.K. Gürsoy, The energy and Sombor index of graphs, MATCH Commun. Math. Comput. Chem 87 (2022), 51–58. https://doi.org/10.46793/match.87-1.051U
[26] Z. Wang, F. Gao, D. Zhao, and H. Liu, Sharp upper bound on the Sombor index of bipartite graphs with a given diameter, J. Appl. Math. Comput. 70 (2024), no. 1, 27–46. https://doi.org/10.1007/s12190-023-01955-8
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 07 November 2025

Files

Share

How to cite

Statistics