AN ALTERNATIVE PROOF OF THE SOMBOR INDEX MINIMIZING PROPERTY OF GREEDY TREES

Abstract

Recently, Gutman defined a new graph invariant which is named the Sombor index SO(G) of a graph G and is computed via the expression (Formula Presented) where 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. Damnjanović et al. have implemented an earlier result obtained by Wang in order to show that, among all the trees TD that have a specified degree sequence D, the greedy tree must attain the minimum Sombor index. Here we provide an alternative proof of this same result by constructing an auxiliary graph invariant named the pseudo-Sombor index and without relying on any other earlier results.