Czechoslovak Mathematical Journal, Vol. 72, No. 4, pp. 1227-1238, 2022


Quasi-tree graphs with the minimal Sombor indices

Yibo Li, Huiqing Liu, Ruiting Zhang

Received April 7, 2022.   Published online September 29, 2022.

Abstract:  The Sombor index $SO(G)$ of a graph $G$ is the sum of the edge weights $\sqrt{d^2_G(u)+d^2_G(v)}$ of all edges $uv$ of $G$, where $d_G(u)$ denotes the degree of the vertex $u$ in $G$. A connected graph $G = (V ,E)$ is called a quasi-tree if there exists $u\in V (G)$ such that $G-u$ is a tree. Denote $\mathscr{Q}(n,k)=\{G \colon G$ is a quasi-tree graph of order $n$ with $G-u$ being a tree and $d_G(u)=k\}$. We determined the minimum and the second minimum Sombor indices of all quasi-trees in $\mathscr{Q}(n,k)$. Furthermore, we characterized the corresponding extremal graphs, respectively.
Keywords:  Sombor index; quasi-tree; tree
Classification MSC:  05C07, 05C09, 05C35


References:
[1] J. A. Bondy, U. S. R. Murty: Graph Theory. Graduate Texts in Mathematics 244. Springer, Berlin (2008). DOI 10.1007/978-1-84628-970-5  | MR 2368647 | Zbl 1134.05001
[2] H. Chen, W. Li, J. Wang: Extremal values on the Sombor index of trees. MATCH Commun. Math. Comput. Chem. 87 (2022), 23-49. DOI 10.46793/match.87-1.023C | Zbl 7582823
[3] R. Cruz, I. Gutman, J. Rada: Sombor index of chemical graphs. Appl. Math. Comput. 399 (2021), Article ID 126018, 10 pages. DOI 10.1016/j.amc.2021.126018 | MR 4212004 | Zbl 07423489
[4] R. Cruz, J. Rada: Extremal values of the Sombor index in unicyclic and bicyclic graphs. J. Math. Chem. 59 (2021), 1098-1116. DOI 10.1007/s10910-021-01232-8 | MR 4232832 | Zbl 1462.05071
[5] R. Cruz, J. Rada, J. M. Sigarreta: Sombor index of trees with at most three branch vertices. Appl. Math. Comput. 409 (2021), Article ID 126414, 9 pages. DOI 10.1016/j.amc.2021.126414 | MR 4271495 | Zbl 07425030
[6] K. C. Das, I. Gutman: On Sombor index of trees. Appl. Math. Comput. 412 (2022), Article ID 126575, 8 pages. DOI 10.1016/j.amc.2021.126575 | MR 4300333 | Zbl 07426979
[7] H. Deng, Z. Tang, R. Wu: Molecular trees with extremal values of Sombor indices. Int. J. Quantum Chem. 121 (2021), Article ID e26622, 9 pages. DOI 10.1002/qua.26622
[8] I. Gutman: Geometric approach to degree-based topological indices: Sombor indices. MATCH Commun. Math. Comput. Chem. 86 (2021), 11-16. Zbl 1474.92154
[9] H. Liu, H. Chen, Q. Xiao, X. Fang, Z. Tang: More on Sombor indices of chemical graphs and their applications to the boiling point of benzenoid hydrocarbons. Int. J. Quantum Chem. 121 (2021), Article ID e26689, 9 pages. DOI 10.1002/qua.26689
[10] H. Liu, I. Gutman, L. You, Y. Huang: Sombor index: Review of extremal results and bounds. J. Math. Chem. 60 (2022), 771-798. DOI 10.1007/s10910-022-01333-y | MR 4402726 | Zbl 07534385
[11] J. Rada, J. M. Rodríguez, J. M. Sigarreta: General properties on Sombor indices. Discrete Appl. Math. 299 (2021), 87-97. DOI 10.1016/j.dam.2021.04.014 | MR 4256885 | Zbl 1465.05042
[12] T. Réti, T. Došlić, A. Ali: On the Sombor index of graphs. Contrib. Math. 3 (2021), 11-18. DOI 10.47443/cm.2021.0006
[13] Z. Wang, Y. Mao, Y. Li, B. Furtula: On relations between Sombor and other degree-based indices. J. Appl. Math. Comput. 68 (2022), 1-17. DOI 10.1007/s12190-021-01516-x  | MR 4370614 | Zbl 07534916
[14] T. Zhou, Z. Lin, L. Miao: The Sombor index of trees and unicyclic graphs with given maximum degree. DML, Discrete Math. Lett. 7 (2021), 24-29. DOI 10.47443/dml.2021.0035 | MR 4256414

Affiliations:   Yibo Li, Huiqing Liu, Ruiting Zhang (corresponding author), Hubei Key Laboratory of Applied Mathematics, Faculty of Mathematics and Statistics, Hubei University, Wuhan 430062, P. R. China, e-mail: yiboli_2019@163.com, hqliu@hubu.edu.cn, deliazhangruiting@163.com


 
PDF available at: