A note on extremal Sombor indices
of trees with a given degree sequence

In a recent private communication, Ivan Gutman asked a number of colleagues to characterize tree(s) of order $n$ with the given degree sequence $\mathcal{D}$ whose Sombor indices are minimum and maximum. Recall that Sombor index $SO(G)$ of a graph $G=(V,E)$ is defined in [2] as

$$SO(G)=\sum_{uv\in E}\sqrt{d_{u}^{2}+d_{v}^{2}},$$

where $d_{u},d_{v}$ are degrees of the vertices $u,v\in V$. Observing that switching edges (i.e., delete edges $ab$ and $cd$, and add edges $ac$ and $bd$) decreases Sombor index under suitable conditions, while keeping degrees intact, we quickly jumped in to show in [1] that a greedy tree necessarily attains the minimum Sombor index among trees with degree sequence $\mathcal{D}$. Actually, the greedy tree is the unique tree that minimizes pseudo-Sombor index (see [1] for details), but in principle there may exist other trees with the same minimum value of Sombor index as the greedy tree for given $\mathcal{D}$. A more detailed reading of references by one of us during the subsequent attempt to determine trees with the maximum Sombor index, revealed that this problem actually fits within the framework of results by Hua Wang [3], which quickly implies both that the greedy tree has the minimum and that an alternating greedy tree has the maximum value of Sombor index among trees with degree sequence $\mathcal{D}$.

For the sake of completeness, let us present here the result of Wang [3]. Assume that the degree sequence $\mathcal{D}$ is ordered in a non-increasing order, and denote by $d_{1}\geq\dots\geq d_{m}$ the degrees of internal vertices (i.e., the elements of $\mathcal{D}$ that are greater than one). Both the greedy tree and the alternating greedy tree are constructed algorithmically. The greedy tree is constructed as follows:

1. (g1)

   Label the root with the largest degree $d_{1}$;

2. (g2)

   Label the neighbors of the root as $d_{2}$, $d_{3}$, …, assigning to each next neighbor the largest available degree;

3. (g3)

   For each labelled vertex in the current level, considered in a non-increasing order of labels, label its children in turn with the largest available degree;

4. (g4)

   Repeat (g3) as long as there are available internal degrees, then add necessary number of leaves so that the degree of each vertex is equal to its label.

The alternating greedy tree is constructed by a recursive procedure:

1. (a1)

   If $m-1\leq d_{m}$, the alternating greedy tree is a tree rooted at the vertex $r$ with $d_{m}$ children, among which $d_{m}-m+1$ are leaves, while the remaining children have degrees $d_{1},\dots,d_{m-1}$;

2. (a2)

   If $m-1\geq d_{m}+1$, create a subtree $T$ rooted at $r$ with $d_{m}-1$ children with degrees $d_{1},\dots,d_{d_{m}-1}$;

3. (a3)

   Let $S$ be the alternating greedy tree corresponding to the sequence $(d_{d_{m}},\dots,\linebreak d_{m-1})$ of internal degrees, and let $v$ be a leaf of $S$ with the smallest degree of its neighbor. The alternating greedy tree for the sequence $(d_{1},\dots,d_{m})$ is obtained by identifying the root $r$ of $T$ with $v$ in $S$.

These two constructions are illustrated in Fig. 1 for the internal degree sequence $(5,4,3,3,3,2,2,2)$. The greedy tree, shown in Fig. 1(a), is produced uniquely by the steps (g1)–(g4). However, several non-isomorphic alternating greedy trees may be produced by the steps (a1)–(a3), as it can happen that the leaf $v$ in the step (a3) can be selected in different non-isomorphic ways. Namely, step (a2) applied to $(5,4,3,3,3,2,2,2)$ produces the subtree $T_{1}$ with the root $r_{1}$, leaving the subsequence $(4,3,3,3,2,2)$ for which one has to produce an alternating greedy tree in step (a3). This calls step (a2) recursively to produce the subtree $T_{2}$ with the root $r_{2}$, and leaves the subsequence $(3,3,3,2)$. Another recursive call to step (a2) produces the subtree $T_{3}$ with the root $r_{3}$, which leaves the subsequence $(3,3)$ for which step (a1) produces the alternating greedy tree $S_{3}$. All these “constituents” are shown in Fig. 1(b). However, going back from these recursive calls and continuing with step (a3) yields several possible choices for the choice of the leaf $v$. First, the root $r_{3}$ of $T_{3}$ may be identified with either of the leaves $v_{1}$ and $v_{2}$ of $S_{3}$. If $r_{3}$ is identified with $v_{1}$, as done in Fig. 1(c) and 1(d), then the root $r_{2}$ of $T_{2}$ may be further identified with either one of the remaining leaves of $S_{3}$ or one of the leaves of $T_{3}$ in the newly formed tree. After this is done, there are still several choices left for the choice of the leaf which should be identified with the root $r_{1}$ of $T_{1}$. Fig. 1(c)–(e) shows some of the final resulting alternating greedy trees (where in Fig. 1(e) the root $r_{3}$ was initially identified with the leaf $v_{2}$).

Generalizing earlier results, Wang [3] considered for a tree $T=(V,E)$ the general form of a topological index defined as

$$R_{f}(T)=\sum_{uv\in E}f(d_{u},d_{v}),$$

where $f\colon\mathbb{N}\times\mathbb{N}\to\mathbb{R}$ is a symmetric function. He proved the following theorem.

Let us now specifically define $f$ as

$$f(x,a)=-\sqrt{x^{2}+a^{2}}$$

so that $R_{f}(T)$ is actually minus Sombor index of $T$. In this case the condition (1) reads as

$$-\sqrt{x^{2}+a^{2}}-\sqrt{y^{2}+b^{2}}\geq-\sqrt{y^{2}+a^{2}}-\sqrt{x^{2}+b^{2}}$$

whenever $x\geq y$ and $a\geq b$, which is equivalent to

$$\sqrt{x^{2}+a^{2}}+\sqrt{y^{2}+b^{2}}\leq\sqrt{y^{2}+a^{2}}+\sqrt{x^{2}+b^{2}}.$$

After squaring and rearranging, this is further equivalent to

$$(x^{2}+a^{2})(y^{2}+b^{2})\leq(y^{2}+a^{2})(x^{2}+b^{2}),$$

and further to

$$0\leq(a^{2}-b^{2})(x^{2}-y^{2}),$$

which is certainly satisfied whenever $x\geq y$ and $a\geq b$ (with strict inequality if both $x>y$ and $a>b$). Hence Theorem 1 holds for minus Sombor index, leading to the following corollary for Sombor index itself.