Greedy trees have minimum Sombor indices

Abstract

Recently, Gutman [MATCH Commun. Math. Comput. Chem. 86 (2021) 11-16] defined a new graph invariant which is named the Sombor index \(\mathrm{SO}(G)\) of a graph \(G\) and is computed via the expression \[ \mathrm{SO}(G) = \sum_{u \sim v} \sqrt{\mathrm{deg}(u)^2 + \mathrm{deg}(v)^2} , \] where \(\mathrm{deg}(u)\) represents the degree of the vertex \(u\) in \(G\) and the summing is performed across all the unordered pairs of adjacent vertices \(u\) and \(v\). Here we take into consideration the set of all the trees \(\mathcal{T}_D\) that have a specified degree sequence \(D\) and show that the greedy tree attains the minimum Sombor index on the set \(\mathcal{T}_D\).