The Euler Sombor (\(EU\)) index of a graph \(G\) is defined as \[EU(\mathit{G})=\sum \limits_{{\mathit{u}}{\mathit{v}}\in E(\mathit{G})} \sqrt{deg_G^2(u)+deg_G^2(v)+deg_G(u)deg_G(v)},\] where \(deg_G(u)\) and \(deg_G(v)\) are the degrees of the vertices \(u\) and \(v\) in the graph \(G\), respectively. Biswaranja Khanra and Shibsankar Das [Euler Sombor index of trees, unicyclic and chemical graphs, MATCH Commun. Math. Comput. Chem., 94 (2025) 525–548] posed an open problem to determine the extremal values and extremal graphs of the Euler Sombor index in the class of all connected graphs with a given domination number. In this paper, we solve this open problem for trees with a given domination number. Furthermore, we determine an upper bound for the Euler Sombor index of trees with a given independence number. We also characterize the corresponding extremal trees. Additionally, we propose a set of open problems for future research.
A topological index is a numerical value that represents a graph and its corresponding molecular structure [29, 30]. Numerous topological indices have been designed by various researchers throughout the world, and they are significant for particular applications in \(QSAR/QSPR\) studies, depending on the algorithm used. These indices play a vital role in environmental chemistry, drug design, and material science. Apart from these applications, researchers have also studied various related fields in order to connect such indices with structural graph parameters. A chemical compound can be modeled as a graph to predict the behaviour of molecules without using the expensive apparatus and labour time required for experimental procedures [19, 11, 18]. In 2021, Gutman proposed the Sombor index as a novel topological descriptor. For any graph \(G\), it is expressed as \[SO(G)=\sum_{uv\in E(G)}\sqrt{deg^2_G(u)+deg^2_G(v)},\] where \(deg_G(u)\) and \(deg_G(v)\) denote the degrees of the vertices incident with the edge \(uv\). For details of mathematical investigations on the Sombor index, one may consult recent papers and review papers [12, 25, 14, 5], together with the references therein.
In some recent studies, a similarly appearing quantity has been encountered [3, 13], namely \[EU(G)=\sum_{uv\in E(G)}\sqrt{deg^2_G(u)+deg^2_G(v)+deg_G(u)deg_G(v)}.\] This quantity is called the Euler–Sombor index. Tang et al. [28] determined the extremal value of the Euler–Sombor index among all molecular trees with a fixed number of vertices and characterized the molecular trees that attain this extremal value. Ali et al. [6] obtained the best possible bounds for a graphical edge-weight-function index of a graph with given parameters, namely matching number, pendent vertices, and maximum degree. Kızılırmak [21] determined the extremal values of the Euler–Sombor index for tricyclic graphs. Albalahi et al. [2] obtained the maximum Euler Sombor index of tricyclic molecular graphs of a given order. Recently, Ali et al. [4] explored the properties of the generalized Gutman–Milovanović index, the generalized elliptic-Sombor index, the generalized Zagreb–Sombor index, and the generalized Euler–Sombor index. Khanra et al. [17] determined the families of trees attaining the first through fifth minimal Euler Sombor indices, and the unicyclic graphs attaining the maximal, as well as the first through third minimal, Euler Sombor indices. For further developments on the Euler–Sombor index, we refer the reader to recent articles [3, 13, 28, 6, 21, 2, 4, 17, 31, 1, 26, 10, 20] and the references cited therein.
In this paper, only simple connected graphs are considered. For such a graph \(G\), we denote the vertex set and edge set by \(V(G)\) and \(E(G)\), respectively. The set of all neighbours of a vertex \(x\) in \(G\) is defined as \[N_G(x)=\{u\in V(G):xu\in E(G)\},\] or simply \(N(x)\) when there is no ambiguity, and \(d(x)=|N(x)|\) is called the degree of \(x\). Let \(G-uv\) be the graph obtained from \(G\) by deleting the edge \(uv\in E(G)\). The subgraph of \(G\) obtained by deleting the vertex \(x\in V(G)\), together with all edges incident with it, is denoted by \(G-x\). Let \(\mathit{S}_n\) and \(\mathit{P}_n\) denote the \(n\)-vertex star and the \(n\)-vertex path, respectively.
The connection between topological indices and domination number has attracted the attention of many researchers [8, 9, 15, 23, 24, 16, 7, 27]. A vertex set \(\mathit{D}\subseteq V\) is a dominating set in \(G\) if every vertex in \(V\backslash \mathit{D}\) is adjacent to at least one vertex in \(\mathit{D}\). The domination number of \(G\) is the minimum cardinality among all dominating sets of \(G\), and it is denoted by \(\Upsilon(G)\). A subset \(S\) of the vertex set of \(G\) is said to be independent if every pair of vertices in \(S\) is non-adjacent in \(G\). The independence number of \(G\) is the maximum cardinality among all independent sets of \(G\), and it is denoted by \(\beta(G)\).
Motivated by Borovi\(\check{c}\)anin and Furtula [8], Hu and Zhong [16], Bermudo, N\(\check{\text{a}}\)poles and Rada [7], Sun and Du [27], and Zhang, Wang, Su and Das [32], Khanra et al. [17] posed the following open problem:
Open Problem. Determine the extremal values and corresponding extremal graphs of the Euler Sombor index in the class of all connected graphs with a given domination number.
In this paper, we address this problem in the context of trees. Specifically, we establish both the upper and lower bounds for the Euler Sombor index of trees with a fixed domination number. Furthermore, we derive an upper bound for the Euler Sombor index of trees with a given independence number and characterize the extremal trees that attain this bound.
Let \[\mathfrak{f}(x,y)=\sqrt{x^2+y^2+xy},\] where \(x,y\geq 1\). The following Lemmas 2.1 and 2.2 are readily obtained.
Lemma 2.1. [2] Let \[\phi_c(x)=\mathfrak{f}(x,c+1)-\mathfrak{f}(x,c) =\sqrt{x^2+(c+1)^2+x(c+1)}-\sqrt{x^2+c^2+xc},\] where \(x\geq 1\) and \(c\geq 1\). The function \(\phi_c(x)\) is decreasing in \(x\).
Lemma 2.2. [6] Let \[\psi_c(x)=\mathfrak{f}(x,c)-\mathfrak{f}(x-1,c) =\sqrt{x^2+c^2+xc}-\sqrt{(x-1)^2+c^2+(x-1)c},\] where \(x\geq 2\) and \(c\geq 1\). The function \(\psi_c(x)\) is increasing in \(x\).
Lemma 2.3. Let \[\begin{aligned} \chi(n)=&(n-1)\sqrt{(n-1)^2+1+(n-1)}-(3\sqrt{19}+\sqrt{7}-6\sqrt{3})n\\ &-(24\sqrt{3}-3\sqrt{7}-9\sqrt{19})-2\sqrt{7}+6\sqrt{3}. \end{aligned}\] Then \(\chi(n)>0\) for \(n\geq 5\).
Proof. Notice that for \(n\geq 5\), \[\begin{aligned} \chi'(n) &=\sqrt{(n-1)^2+1+(n-1)} +\frac{(n-1)[1+2(n-1)]}{2\sqrt{(n-1)+(n-1)^2+1}}\\ &\quad-3\sqrt{19}-\sqrt{7}+6\sqrt{3}\\ &\geq \sqrt{21}+\frac{18}{\sqrt{21}}-3\sqrt{19}-\sqrt{7}+6\sqrt{3}\\ &\approx 3.1804>0. \end{aligned}\] Therefore, \[\chi(n)\geq\chi(5)=4\sqrt{21}-6\sqrt{19}-4\sqrt{7}+12\sqrt{3}\approx 2.3785>0.\] ◻
Lemma 2.4. Let \[\begin{aligned} \rho(b,b_1)&=\sqrt{b^2+1+b} +(b_1-1)\left(\sqrt{b^2+1+b}-\sqrt{(b-1)^2+1+(b-1)}\right)\\ &\qquad +(b-b_1)\left(\sqrt{b^2+4+2b}-\sqrt{(b-1)^2+4+2(b-1)}\right), \end{aligned}\] where \(b_1\geq 2\), \(b\geq 4\), and \(b_1< b\). The function \(\rho(b,b_1)\) is increasing with respect to both \(b\) and \(b_1\).
Proof. Note that \[\begin{aligned} \rho(b,b_1)&=b_1\Big[\big(\sqrt{(b-1)^2+4+2(b-1)} -\sqrt{(b-1)^2+1+(b-1)}\big)\\ &\quad-\big(\sqrt{b^2+4+2b}-\sqrt{b^2+1+b}\big)\Big] +b\big(\sqrt{b^2+4+2b}\\ &\quad-\sqrt{(b-1)^2+4+2(b-1)}\big) +\sqrt{(b-1)^2+1+(b-1)}. \end{aligned}\] Using Lemma 2.1, we have \[\begin{aligned} &\big(\sqrt{(b-1)^2+4+2(b-1)} -\sqrt{(b-1)^2+1+(b-1)}\big)\\ &\quad-\big(\sqrt{b^2+4+2b}-\sqrt{b^2+1+b}\big) =\phi_1(b-1)-\phi_1(b)>0. \end{aligned}\] Hence, \(\rho(b,b_1)\) is increasing with respect to \(b_1\). Furthermore, \[\begin{aligned} \frac{\partial\rho(b,b_1)}{\partial b} =&b_1\bigg[\left(\frac{2(b-1)+2}{2\sqrt{(b-1)^2+4+2(b-1)}} -\frac{2(b-1)+1}{2\sqrt{(b-1)^2+1+(b-1)}}\right)\\ &\quad-\left(\frac{2b+2}{2\sqrt{b^2+4+2b}} -\frac{2b+1}{2\sqrt{b^2+1+b}}\right)\bigg]\\ &+\left[\sqrt{b^2+4+2b}-\sqrt{(b-1)^2+4+2(b-1)}\right]\\ &+\frac{2(b-1)+1}{\sqrt{(b-1)^2+1+(b-1)}}\\ &+b\left(\frac{2b+2}{2\sqrt{b^2+4+2b}} -\frac{2(b-1)+2}{2\sqrt{(b-1)^2+4+2(b-1)}}\right). \end{aligned}\]
Let \[l_1(x)=\dfrac{x+1}{\sqrt{x^2+4+2x}} -\dfrac{2x+1}{2\sqrt{x^2+1+x}},\] where \(x\geq 2\). Then \[\begin{aligned} l_1^{'}(x) =&\dfrac{1}{\sqrt{x^2+2x+4}} +\dfrac{(x+1)(2x+2)}{2(x^2+2x+4)^{\frac{3}{2}}}\\ &-\dfrac{1}{\sqrt{x^2+x+1}} +\dfrac{(2x+1)^2}{4(x^2+x+1)^{\frac{3}{2}}}>0. \end{aligned}\] Consequently, \[\begin{aligned} &\left(\dfrac{b-1+1}{\sqrt{(b-1)^2+4+2(b-1)}} -\dfrac{2(b-1)+1}{2\sqrt{(b-1)^2+1+(b-1)}}\right)\\ &\quad-\left(\dfrac{b+1}{\sqrt{b^2+4+2b}} -\dfrac{2b+1}{2\sqrt{b^2+1+b}}\right) =l_1(b-1)-l_1(b)<0. \end{aligned}\]
Since \(b_1<b\), we have \[\begin{aligned} \frac{\partial \rho(b,b_1)}{\partial b} &> b\bigg[\left(\frac{(b-1)+1}{\sqrt{(b-1)^2+4+2(b-1)}} -\frac{2(b-1)+1}{2\sqrt{(b-1)^2+1+(b-1)}}\right)\\ &\quad-\left(\frac{b+1}{\sqrt{b^2+4+2b}} -\frac{2b+1}{2\sqrt{b^2+1+b}}\right)\bigg]\\ &\quad+\left[\sqrt{b^2+4+2b}-\sqrt{(b-1)^2+4+2(b-1)}\right]\\ &\quad+b\left[\frac{b+1}{\sqrt{b^2+4+2b}} -\frac{(b-1)+1}{\sqrt{(b-1)^2+4+2(b-1)}}\right]\\ &\quad+\frac{2(b-1)+1}{\sqrt{(b-1)^2+1+(b-1)}}\\ &=\left[\sqrt{b^2+4+2b}-\sqrt{(b-1)^2+4+2(b-1)}\right]\\ &\quad+\frac{b(2b+1)}{2\sqrt{b^2+1+b}} -\frac{(b-1)[2(b-1)+1]}{2\sqrt{(b-1)^2+1+(b-1)}}. \end{aligned}\]
Let \[l_2(x)=\dfrac{x(2x+1)}{2\sqrt{x^2+1+x}}.\] Then, for \(x\geq 2\), \[l_2^{'}(x)=\dfrac{2x+1}{2\sqrt{x^2+1+x}} +\dfrac{x}{\sqrt{x^2+x+1}} -\dfrac{x(2x+1)^2}{4(x^2+x+1)^{\frac{3}{2}}}>0.\] Therefore, \[\dfrac{b(2b+1)}{2\sqrt{b^2+1+b}} -\dfrac{(b-1)[2(b-1)+1]}{2\sqrt{(b-1)^2+1+(b-1)}}=l_2(b)-l_2(b-1)>0.\] Thus, \[\dfrac{\partial\rho(b,b_1)}{\partial b}>0,\] and \(\rho(b,b_1)\) is increasing with respect to \(b\). ◻
A family of trees \(\mathcal{T}\) is defined recursively as follows. We consider the path of order \(3l\), with \(l\geq 1\), in \(\mathcal{T}\), and construct new trees in the family \(\mathcal{T}\) in the following two ways.
If \(\mathit{T}\in \mathcal{T}\), \(w\) is a pendent vertex of \(\mathit{T}\), and \(P=v_1v_2\cdots v_{3q}\) is any path with \(q \geq 1\), then \(\mathit{T}'=(V(\mathit{T}'), E(\mathit{T}'))\), where \[V(\mathit{T}')=V(P)\cup V(\mathit{T})\] and \[E(\mathit{T}')=E(P)\cup E(\mathit{T})\cup \{wv_1\},\] belongs to \(\mathcal{T}\).
If \(\mathit{T}\in \mathcal{T}\) satisfies that there exists a vertex \(u\) belonging to a minimum dominating set of \(\mathit{T}\), with \(N_T(u)=\{u_1,u_2\}\) such that \(deg_T(u_1)=2=deg_T(u_2)\), and if \(P=v_1v_2\cdots v_{3q+1}\) is any path with \(q\geq 1\), then the tree \(\mathit{T}''=(V(\mathit{T}''),E(\mathit{T}''))\), where \[V(\mathit{T}'')=V(P)\cup V(\mathit{T})\] and \[E(\mathit{T}'')=E(P)\cup E(\mathit{T})\cup \{uv_1\},\] belongs to \(\mathcal{T}\).
Let \(\mathcal{T}_{n,\Upsilon}\) be the set of all trees \(\mathit{T} \in \mathcal{T}\) with domination number \(\Upsilon\). Let \[\mathfrak{g}(n,\Upsilon)=(3\sqrt{19}+\sqrt{7}-6\sqrt{3})n +(24\sqrt{3}-9\sqrt{19}-3\sqrt{7})\Upsilon+2\sqrt{7}-6\sqrt{3}.\]
Lemma 3.1. Let \(\mathit{T}\in \mathcal{T}_{n,\Upsilon}\). Then \[EU(\mathit{T})=\mathfrak{g}(n,\Upsilon).\]
Proof. Since \(\mathit{T}\in \mathcal{T}_{n,\Upsilon}\), we have \[\begin{cases} n_1+n_2+n_3=n,\\ n_1+2n_2+3n_3=2(n-1),\\ n_3+\dfrac{n-n_3-3n_3}{3}=\Upsilon. \end{cases}\] Thus, \[n_1=n-3\Upsilon+2,\qquad n_2=6\Upsilon-n-2,\qquad n_3=n-3\Upsilon.\] By the definitions of the Euler–Sombor index and the family \(\mathcal{T}\), we have \[\begin{aligned} EU(\mathit{T}) &=3n_3\mathfrak{f}(2,3)+n_1\mathfrak{f}(1,2) +(n-1-3n_3-n_1)\mathfrak{f}(2,2)\\ &=3\sqrt{19}(n-3\Upsilon)+(n-3\Upsilon+2)\sqrt{7} +[n-1-(4n-12\Upsilon+2)]2\sqrt{3}\\ &=(3\sqrt{19}+\sqrt{7}-6\sqrt{3})n +(24\sqrt{3}-9\sqrt{19}-3\sqrt{7})\Upsilon +2\sqrt{7}-6\sqrt{3}\\ &=\mathfrak{g}(n,\Upsilon). \end{aligned}\] This completes the proof. ◻
Theorem 3.2. Let \(\mathit{T}\in \mathbb{T}_{n,\Upsilon}\). Then \[EU(\mathit{T})\geq \mathfrak{g}(n,\Upsilon).\] Equality holds if and only if \(\mathit{T}\in \mathcal{T}_{n,\Upsilon}\).
Proof. If \(n=3\), then \[EU(\mathit{P}_3)=2\sqrt{7}=\mathfrak{g}(3,1).\] If \(n=4\), then \[EU(\mathit{P}_4)=2\sqrt{7}+2\sqrt{3}>\mathfrak{g}(4,2)=18\sqrt{3}-6\sqrt{19}\] and \[EU(\mathit{S}_4)=3\sqrt{13}>\mathfrak{g}(4,1)=3\sqrt{19}+3\sqrt{7}-6\sqrt{3}.\] Suppose that \(n\geq 5\) and that the result holds for all trees of order \(n-1\). Let \(u_1u_2\cdots u_{d+1}\) denote the vertices along a diametral path in the tree \(T\), where \(d\) is the diameter of \(T\). If \(d=2\), then \(\mathit{T}\cong \mathit{S}_{n}\) and \(\Upsilon(\mathit{S}_n)=1\). Using Lemma 2.3, for \(n\geq 5\), we have \[\begin{aligned} EU(\mathit{S}_n)-\mathfrak{g}(n,1) &=(n-1)\sqrt{(n-1)^2+1+(n-1)} -(3\sqrt{19}+\sqrt{7}-6\sqrt{3})n\\ &\quad-(24\sqrt{3}-3\sqrt{7}-9\sqrt{19}) -2\sqrt{7}+6\sqrt{3}>0. \end{aligned}\] Thus, the theorem holds when \(d=2\). Henceforth, assume that \(d\geq 3\). Let \[deg_T(u_2)=\alpha,\qquad N_T(u_2)=\{u_1,u_3,x_1,x_2,\cdots,x_{\alpha-2}\},\] and \[deg_T(u_3)=\beta,\qquad N_T(u_3)=\{u_2,u_4,y_1,y_2,\cdots,y_{\beta-2}\},\] where \(\alpha,\beta \geq 2\). We now consider the following cases.
Case 1. \(deg_T(u_2)=\alpha\geq 3\).
Note that \(deg_T(x_i)=1\) for every \(1\leq i \leq \alpha-2\). Let \(\mathit{T}_1=\mathit{T}-u_1\). Then \(\mathit{T}_1\in \mathbb{T}_{n-1,\Upsilon}\). Using induction, we have \[\begin{aligned} EU(\mathit{T}) &=EU(\mathit{T}_1)+\mathfrak{f}(\alpha,1) +(\alpha-2)[\mathfrak{f}(\alpha,1)-\mathfrak{f}(\alpha-1,1)]\\ &\quad+\mathfrak{f}(\alpha,\beta)-\mathfrak{f}(\alpha-1,\beta)\\ &\geq \mathfrak{g}(n-1,\Upsilon)+\sqrt{\alpha^2+1+\alpha}\\ &\quad+(\alpha-2)\left(\sqrt{\alpha^2+1+\alpha} -\sqrt{(\alpha-1)^2+1+(\alpha-1)}\right)\\ &\quad+\sqrt{\alpha^2+\beta^2+\alpha\beta} -\sqrt{(\alpha-1)^2+\beta^2+\beta(\alpha-1)}. \end{aligned}\]
Subcase 1.1. \(\alpha\geq 4\).
By Lemma 2.2, we have \[\begin{aligned} EU(\mathit{T}) &>\mathfrak{g}(n-1,\Upsilon)+\sqrt{\alpha^2+1+\alpha}\\ &\quad+(\alpha-2)\left(\sqrt{\alpha^2+1+\alpha} -\sqrt{(\alpha-1)^2+1+(\alpha-1)}\right)\\ &\geq \mathfrak{g}(n-1,\Upsilon)+\sqrt{21}+2(\sqrt{21}-\sqrt{13})\\ &=\mathfrak{g}(n,\Upsilon)-3\sqrt{19}-\sqrt{7}+6\sqrt{3}+3\sqrt{21}-2\sqrt{13}\\ &\approx \mathfrak{g}(n,\Upsilon)+1.2065>\mathfrak{g}(n,\Upsilon). \end{aligned}\]
Subcase 1.2. \(\alpha=3\) and \(\beta\leq 4\).
By Lemma 2.1, we have \[\begin{aligned} EU(\mathit{T}) &\geq \mathfrak{g}(n-1,\Upsilon)+\sqrt{\alpha^2+1+\alpha}\\ &\quad+(\alpha-2)\left(\sqrt{\alpha^2+1+\alpha} -\sqrt{(\alpha-1)^2+1+(\alpha-1)}\right)\\ &\quad+\sqrt{\alpha^2+16+4\alpha}-\sqrt{(\alpha-1)^2+16+4(\alpha-1)}\\ &= \mathfrak{g}(n-1,\Upsilon)+\sqrt{13}+(\sqrt{13}-\sqrt{7})+\sqrt{37}-\sqrt{28}\\ &=\mathfrak{g}(n,\Upsilon)-3\sqrt{19}-4\sqrt{7}+6\sqrt{3}+2\sqrt{13}+\sqrt{37}\\ &\approx \mathfrak{g}(n,\Upsilon)+0.0265>\mathfrak{g}(n,\Upsilon). \end{aligned}\]
Subcase 1.3. \(\alpha=3\) and \(\beta\geq 5\).
Let \(\mathit{T}_1'=\mathit{T}-\{u_1,u_2,x_1\}\). In this case, there is a dominating set \(\mathit{D}\) with \(|\mathit{D}|=\Upsilon\) in \(\mathit{T}\) such that \(u_2\in \mathit{D}\), and either \(u_3\in \mathit{D}\) or \(u_3\in N[\mathit{D}\backslash \{u_2\}]\). Hence, \[\Upsilon(\mathit{T})=\Upsilon(\mathit{T}_1')+1\] and \[\mathit{T}_1'\in \mathbb{T}_{n-3,\Upsilon-1}.\] Using induction and Lemma 2.2, we have \[\begin{aligned} EU(\mathit{T}) &=EU(\mathit{T}_1')+\mathfrak{f}(3,\beta)+2\mathfrak{f}(3,1) +\mathfrak{f}(\beta,deg_{T}(u_4)) -\mathfrak{f}(\beta-1,deg_{\mathit{T}_1'}(u_4))\\ &\quad+\sum_{i=1}^{\beta-2}\Big[\mathfrak{f}(\beta,deg_{\mathit{T}}(y_i)) -\mathfrak{f}(\beta-1,deg_{\mathit{T}_1'}(y_i))\Big]\\ &>\mathfrak{g}(n-3,\Upsilon-1)+\sqrt{\beta^2+9+3\beta}+2\sqrt{13}\\ &\geq \mathfrak{g}(n,\Upsilon)-6\sqrt{3}+2\sqrt{13}+7\\ &\approx \mathfrak{g}(n,\Upsilon)+3.8188>\mathfrak{g}(n,\Upsilon). \end{aligned}\]
Case 2. \(deg_T(u_2)=2\) for every diameter \(u_1u_2\cdots u_{d+1}\).
Subcase 2.1. \(deg_T(u_3)=\beta \geq 3\).
Denote \(deg_T(u_4)=\eta\). By the previous case, we may assume that \(deg_T(y_i)\leq 2\) for every \(1 \leq i \leq \beta-2\). Let \(\mathit{T}_2=\mathit{T}-\{u_1,u_2\}\). Since there exists a dominating set \(\mathit{D}\) with \(|\mathit{D}|=\Upsilon\) in \(\mathit{T}\) such that \(u_2\in \mathit{D}\), and either \(u_3\in \mathit{D}\) or \(u_3\in N[\mathit{D}\backslash\{u_2\}]\), we obtain \[\Upsilon(\mathit{T})=\Upsilon(T_2)+1\] and \[T_2\in \mathbb{T}_{n-2,\Upsilon-1}.\] Using induction and Lemmas 2.1 and 2.2, we have \[\begin{aligned} EU(\mathit{T}) &=EU(T_2)+\mathfrak{f}(2,\beta)+\mathfrak{f}(2,1) +\mathfrak{f}(\beta,deg_T(u_4)) -\mathfrak{f}(\beta-1, deg_{T_2}(u_4))\\ &\quad+\sum_{i=1}^{\beta-2} \Big[\mathfrak{f}(\beta,deg_T(y_i)) -\mathfrak{f}(\beta-1,deg_{T_2}(y_i))\Big]\\ &\geq \mathfrak{g}(n-2,\Upsilon-1)+\sqrt{\beta^2+4+2\beta} +\sqrt{7} +\sqrt{\beta^2+\eta^2+\beta \eta}\\ &\quad-\sqrt{(\beta-1)^2+\eta^2+(\beta-1)\eta}\\ &\quad+(\beta-2)\left(\sqrt{\beta^2+4+2\beta} -\sqrt{(\beta-1)^2+4+2(\beta-1)}\right)\\ &>\mathfrak{g}(n-2,\Upsilon-1)+\sqrt{\beta^2+4+2\beta} +\sqrt{7}\\ &\quad+(\beta-2)\left(\sqrt{\beta^2+4+2\beta} -\sqrt{(\beta-1)^2+4+2(\beta-1)}\right)\\ &\geq \mathfrak{g}(n-2,\Upsilon-1)+\sqrt{19}+\sqrt{7}+\sqrt{19}-\sqrt{12}\\ &=\mathfrak{g}(n,\Upsilon)+5\sqrt{19}+2\sqrt{7}-14\sqrt{3}\\ &\approx \mathfrak{g}(n,\Upsilon)+2.8373>\mathfrak{g}(n,\Upsilon). \end{aligned}\]
Subcase 2.2. \(deg_T(u_3)=2\).
We denote \[N_T(u_4)=\{u_3,u_5,s_1,s_2,\cdots, s_{\eta-2}\}\] and \[deg_T(u_5)=\mu.\] For \(1\leq i \leq \eta-2\), if there are \(s',s''\in V(\mathit{T})\) such that \(s'\in N_T(s_i)\) and \(s''\in N_T(s')\), then \[s''s's_i u_4u_5\cdots u_{d+1}\] is a diameter of \(\mathit{T}\). If \(s_i\) is a support vertex with \(deg_T(s_i)\geq 3\), then, similarly to Case 1, we can prove that \[EU(\mathit{T})>\mathfrak{g}(n,\Upsilon).\] Thus, by the preceding cases, we assume that \[deg_T(s_i)\leq 2,\qquad 1\leq i \leq \eta-2.\]
Subcase 2.2.1. \(deg_T(u_4)=\eta\geq 3\).
Let \(\mathit{T}_3=\mathit{T}-\{u_1,u_2,u_3\}\). Then \[\mathit{T}_3\in \mathbb{T}_{n-3,\Upsilon-1}.\] Using induction and Lemmas 2.1 and 2.2, we have \[\begin{aligned} EU(\mathit{T}) &=EU(\mathit{T}_3)+\mathfrak{f}(2,\eta)+\mathfrak{f}(2,2)+\mathfrak{f}(2,1) +\mathfrak{f}(\eta,\mu)-\mathfrak{f}(\eta-1,\mu)\\ &\quad+\sum_{i=1}^{\eta-2} [\mathfrak{f}(\eta,deg_T(s_i))-\mathfrak{f}(\eta-1,deg_{T_3}(s_i))]\\ &\geq \mathfrak{g}(n-3,\Upsilon-1)+\sqrt{\eta^2+4+2\eta} +2\sqrt{3}+\sqrt{7}\\ &\quad+\sqrt{\eta^2+\mu^2+\eta \mu} -\sqrt{(\eta-1)^2+\mu^2+\mu(\eta-1)}\\ &\quad+(\eta-2)\left(\sqrt{\eta^2+4+2\eta} -\sqrt{(\eta-1)^2+4+2(\eta-1)}\right)\\ &>\mathfrak{g}(n-3,\Upsilon-1)+\sqrt{\eta^2+4+2\eta} +2\sqrt{3}+\sqrt{7}\\ &\quad+(\eta-2)\left(\sqrt{\eta^2+4+2\eta} -\sqrt{(\eta-1)^2+4+2(\eta-1)}\right)\\ &\geq \mathfrak{g}(n-3,\Upsilon-1)+\sqrt{19}+2\sqrt{3}+\sqrt{7} +\sqrt{19}-2\sqrt{3}\\ &= \mathfrak{g}(n,\Upsilon)+2\sqrt{19}-6\sqrt{3}+\sqrt{7}\\ &\approx \mathfrak{g}(n,\Upsilon)+0.9712>\mathfrak{g}(n,\Upsilon). \end{aligned}\]
Subcase 2.2.2. \(deg_T(u_4)=\eta=2\).
Subcase 2.2.2.1. There is a minimum dominating set \(\mathit{D}\) with \(u_4\in \mathit{D}\) in \(\mathit{T}\).
Let \(\mathit{T}_4=\mathit{T}-\{u_1,u_2\}\). We have \[\begin{aligned} EU(\mathit{T}) &=EU(\mathit{T}_4)+\mathfrak{f}(2,2)-\mathfrak{f}(2,1) +\mathfrak{f}(2,2)+\mathfrak{f}(2,1)\\ &\geq \mathfrak{g}(n-2,\Upsilon-1)+4\sqrt{3}\\ &= \mathfrak{g}(n,\Upsilon)+3\sqrt{19}+\sqrt{7}-8\sqrt{3}\\ &\approx \mathfrak{g}(n,\Upsilon)+1.8660>\mathfrak{g}(n,\Upsilon). \end{aligned}\]
Subcase 2.2.2.2. \(u_4\notin \mathit{D}\) for every minimum dominating set \(\mathit{D}\) in \(\mathit{T}\).
We denote \[N_T(u_5)=\{u_4,v_1,v_2,\cdots,v_{\mu-1}\}.\]
Subcase 2.2.2.2.1. \(deg_T(u_5)=\mu=2\).
Let \(\mathit{T}_5=\mathit{T}-\{u_1,u_2,u_3\}\). Thus, \[\begin{aligned} EU(\mathit{T}) &=EU(\mathit{T}_5)+\mathfrak{f}(2,2)-\mathfrak{f}(2,1) +2\mathfrak{f}(2,2)+\mathfrak{f}(2,1)\\ &\geq \mathfrak{g}(n-3,\Upsilon-1)+6\sqrt{3}\\ &= \mathfrak{g}(n,\Upsilon)-9\sqrt{19}-3\sqrt{7}+18\sqrt{3} +9\sqrt{19}+3\sqrt{7}-24\sqrt{3}+3\sqrt{3}\\ &=\mathfrak{g}(n,\Upsilon). \end{aligned}\] Equality holds only if \(\mathit{T}_5\in \mathcal{T}_{n-3,\Upsilon-1}\), which implies that \(\mathit{T}\in \mathcal{T}_{n,\Upsilon}\).
Subcase 2.2.2.2.2. \(deg_T(u_5)=\mu\geq 3\).
Subcase 2.2.2.2.2.1. For every \(1 \leq i \leq \mu-1\), \(deg(v_i)\leq 2\).
Let \(\mathit{T}_6=\mathit{T}-\{u_1,u_2,u_3,u_4\}\). Then \[\mathit{T}_6\in \mathbb{T}_{n-4,\Upsilon-1}.\] Using induction and Lemmas 2.1 and 2.2, we have \[\begin{aligned} EU(T) &=EU(T_6)+\mathfrak{f}(2,\mu)+2\mathfrak{f}(2,2)+\mathfrak{f}(2,1) +\sum_{i=1}^{\mu-1}\Big[\mathfrak{f}(\mu,deg_T(v_i))\\ &\quad-\mathfrak{f}(\mu-1,deg_{T_6}(v_i))\Big]\\ &\geq \mathfrak{g}(n-4,\Upsilon-1)+\sqrt{\mu^2+4+2\mu} +4\sqrt{3}+\sqrt{7}\\ &\quad+(\mu-1)\left(\sqrt{\mu^2+4+2\mu} -\sqrt{(\mu-1)^2+4+2(\mu-1)}\right)\\ &\geq \mathfrak{g}(n-4,\Upsilon-1)+\sqrt{19}+4\sqrt{3}+\sqrt{7} +2(\sqrt{19}-\sqrt{12})\\ &=\mathfrak{g}(n,\Upsilon). \end{aligned}\] Equality holds if and only if \(T_6\in \mathcal{T}_{n-4,\Upsilon-1}\), \(deg_T(u_5)=\mu=3\), and \(deg_T(v_1)=deg_T(v_2)=2\), which implies that \(\mathit{T}\in \mathcal{T}_{n,\Upsilon}\).
Subcase 2.2.2.2.2.2. \[\nu=\max\{deg_T(v_1),deg_T(v_2),\cdots,deg_T(v_{\mu-1})\}\geq 3.\] Assume, without loss of generality, that \(deg_T(v_1)=\nu\). We denote \[N_T(v_1)=\{u_5,w_1,w_2,\cdots,w_{\nu-1}\}.\] Now suppose that \(deg_T(w_i)\leq 2\) for \(1\leq i \leq \nu-1\). Consider two components \(T_7\) and \(T_8\) which are disjoint in \(\mathit{T}-u_5v_1\), containing the vertices \(u_5\) and \(v_1\), respectively. Using induction and Lemmas 2.1 and 2.2, we have \[\begin{aligned} EU(\mathit{T}) &=EU(T_7)+EU(T_8)+\mathfrak{f}(\mu,2)-\mathfrak{f}(\mu-1,2)+\mathfrak{f}(\nu,\mu)\\ &\quad+\sum_{i=2}^{\mu-1} \Big[\mathfrak{f}(\mu,deg_T(v_i)) -\mathfrak{f}(\mu-1,deg_{T_7}(v_i))\Big]\\ &\quad+\sum_{j=1}^{\nu-1} \Big[\mathfrak{f}(\nu,deg_T(w_j)) -\mathfrak{f}(\nu-1,deg_{T_8}(w_j))\Big]\\ &\geq \mathfrak{g}(n,\Upsilon)+2\sqrt{7}-6\sqrt{3} +\sqrt{\mu^2+4+2\mu}-\sqrt{(\mu-1)^2+4+2(\mu-1)}\\ &\quad+\sqrt{\nu^2+\mu^2+\nu\mu} +(\mu-2)\left(\sqrt{\mu^2+\nu^2+\mu \nu} -\sqrt{(\mu-1)^2+\nu^2+(\mu-1)\nu}\right)\\ &\quad+(\nu-1)\left(\sqrt{\nu^2+4+2\nu} -\sqrt{(\nu-1)^2+4+2(\nu-1)}\right)\\ &>\mathfrak{g}(n,\Upsilon)+2\sqrt{7}-6\sqrt{3} +\sqrt{\mu^2+4+2\mu}-\sqrt{(\mu-1)^2+4+2(\mu-1)}\\ &\quad+\sqrt{\nu^2+\mu^2+\mu\nu} +(\nu-1)\left[\sqrt{\nu^2+4+2\nu} -\sqrt{(\nu-1)^2+4+2(\nu-1)}\right]\\ &\geq \mathfrak{g}(n,\Upsilon)+2\sqrt{7}-8\sqrt{3} +\sqrt{19}+3\sqrt{3}+2(\sqrt{19}-2\sqrt{3})\\ &\approx \mathfrak{g}(n,\Upsilon)+2.7797>\mathfrak{g}(n,\Upsilon). \end{aligned}\] The proof is complete. ◻
Let \(\mathfrak{T}_{n,\Upsilon}\) be the family of trees obtained from the star \(\mathit{S}_{n-\Upsilon+1}\) by adding a pendent edge to each of its \(\Upsilon-1\) pendent vertices. Note that for \(\mathit{T}\in \mathbb{T}_{n,\Upsilon}\) with maximum degree \(n-\Upsilon\), we have \(\mathit{T}\cong \mathfrak{T}_{n,\Upsilon}\). Let \[\begin{aligned} \mathfrak{h}(n,\Upsilon) &=EU(\mathcal{T}_{n,\Upsilon})\\ &=(n-2\Upsilon+1)\sqrt{(n-\Upsilon)^2+1+(n-\Upsilon)}\\ &\quad+(\Upsilon-1)\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)} +(\Upsilon-1)\sqrt{7}. \end{aligned}\]
Theorem 3.3. Let \(\mathit{T}\in \mathbb{T}_{n,\Upsilon}\). Then \[EU(\mathit{T})\leq \mathfrak{h}(n,\Upsilon).\] Equality holds if and only if \(\mathit{T}\cong \mathfrak{T}_{n,\Upsilon}\).
Proof. If \(n=3\), then \[EU(\mathit{P}_3)=2\sqrt{7}=\mathfrak{h}(3,1).\] If \(n=4\), then \[EU(\mathit{P}_4)=2\sqrt{7}+2\sqrt{3}=\mathfrak{h}(4,2)\] and \[EU(\mathit{S}_4)=3\sqrt{13}=\mathfrak{h}(4,1).\] Suppose that \(n\geq 5\) and that the result holds for all trees of order \(n-1\). Let \(u_1u_2\cdots u_{d+1}\) denote the vertices along a diametral path in the tree \(T\), where \(d\) is the diameter of \(T\). If \(d=2\), then \(\mathit{T}\cong \mathit{S}_n\), \(\Upsilon(\mathit{S}_n)=1\), and \[EU(\mathit{S}_n)=(n-1)\sqrt{(n-1)^2+1+(n-1)}=\mathfrak{h}(n,1).\] Thus, the result is true. Henceforth, assume that \(d\geq 3\) and \(\Upsilon(\mathit{T})\geq 2\). Let \[deg_T(u_2)=\alpha\geq 2,\qquad N_T(u_2)=\{u_1,u_3,x_1,x_2,\cdots,x_{\alpha-2}\},\] and \[deg_T(u_3)=\beta\geq 2,\qquad N_T(u_3)=\{u_2,u_4,y_1,y_2,\cdots,y_{\beta-2}\}.\] Let \[T_1=\mathit{T}-\{u_1\}.\] We now consider two cases.
Case 1. \(\Upsilon(T_1)=\Upsilon(\mathit{T})\).
By induction and Lemmas 2.1 and 2.2, we have \[\begin{aligned} EU(\mathit{T}) &=EU(T_1)+\mathfrak{f}(\alpha,1)+\mathfrak{f}(\alpha,\beta) -\mathfrak{f}(\alpha-1,\beta) +\sum_{i=1}^{\alpha-2} \big[\mathfrak{f}(\alpha,1)-\mathfrak{f}(\alpha-1,1)\big]\\ &\leq \mathfrak{h}(n-1,\Upsilon)+\sqrt{\alpha^2+1+\alpha} +\sqrt{\alpha^2+\beta^2+\alpha \beta}\\ &\quad-\sqrt{(\alpha-1)^2+\beta^2+(\alpha-1)\beta}\\ &\quad+(\alpha-2)\left(\sqrt{\alpha^2+1+\alpha} -\sqrt{(\alpha-1)^2+1+(\alpha-1)}\right)\\ &\leq \mathfrak{h}(n,\Upsilon) -(n-2\Upsilon+1)\left(\sqrt{(n-\Upsilon)^2+1+(n-\Upsilon)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\right)\\ &\quad-(\Upsilon-1)\left(\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)}\right)\\ &\quad-\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)} +\sqrt{\alpha^2+1+\alpha}\\ &\quad+\sqrt{\alpha^2+4+2\alpha} +(\alpha-2)\left(\sqrt{\alpha^2+1+\alpha} -\sqrt{(\alpha-1)^2+1+(\alpha-1)}\right)\\ &\quad-\sqrt{(\alpha-1)^2+4+2(\alpha-1)}\\ &\leq \mathfrak{h}(n,\Upsilon) -(n-2\Upsilon+1)\left(\sqrt{(n-\Upsilon)^2+1+(n-\Upsilon)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\right)\\ &\quad-(\Upsilon-1)\left(\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)}\right)\\ &\quad-\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\\ &\quad+\sqrt{(n-2\Upsilon+2)^2+1+(n-2\Upsilon+2)}\\ &\quad+\sqrt{(n-2\Upsilon+2)^2+4+2(n-2\Upsilon+2)}\\ &\quad-\sqrt{(n-2\Upsilon+1)^2+4+2(n-2\Upsilon+1)}\\ &\quad+(n-2\Upsilon)\left(\sqrt{(n-2\Upsilon+2)^2+1+(n-2\Upsilon+2)}\right.\\ &\quad\left.-\sqrt{(n-2\Upsilon+1)^2+1+(n-2\Upsilon+1)}\right), \end{aligned}\] since \(\Upsilon\leq \frac{n-(\alpha-2)}{2}\), i.e., \(\alpha\leq n-2\Upsilon+2\).
If \(\Upsilon=2\), then \[EU(\mathit{T})\leq \mathfrak{h}(n,\Upsilon).\] The equality holds if and only if \(\beta=2\) and \(n=\alpha+2\), which implies that \(\mathit{T}\cong \mathfrak{T}_{n,2}\). If \(\Upsilon\geq 3\), then \(n-\Upsilon>n-2\Upsilon+2\). Using Lemma 2.2, we have \[\begin{aligned} EU(\mathit{T}) &\leq \mathfrak{h}(n,\Upsilon) +(n-2\Upsilon+1)\bigg[ \left(\sqrt{(n-2\Upsilon+2)^2+1+(n-2\Upsilon+2)}\right.\\ &\quad\left.-\sqrt{(n-2\Upsilon+1)^2+1+(n-2\Upsilon+1)}\right) -\left(\sqrt{(n-\Upsilon)^2+1+(n-\Upsilon)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\right)\bigg]\\ &\quad+(\Upsilon-2)\left(\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)} -\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)}\right)\\ &\quad+\sqrt{(n-2\Upsilon+1)^2+1+(n-2\Upsilon+1)} -\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\\ &\quad+\Big[ \left(\sqrt{(n-2\Upsilon+2)^2+4+2(n-2\Upsilon+2)}\right.\\ &\quad\left.-\sqrt{(n-2\Upsilon+1)^2+4+2(n-2\Upsilon+1)}\right)\\ &\quad-\left(\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)} -\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)}\right)\Big]\\ &=\mathfrak{h}(n,\Upsilon) +(n-2\Upsilon+1)[\psi_1(n-2\Upsilon+2)-\psi_1(n-\Upsilon)]\\ &\quad+(\Upsilon-2)\left(\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)} -\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)}\right)\\ &\quad+\sqrt{(n-2\Upsilon+1)^2+1+(n-2\Upsilon+1)} -\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\\ &\quad+[\psi_2(n-2\Upsilon+2)-\psi_2(n-\Upsilon)] <\mathfrak{h}(n,\Upsilon). \end{aligned}\]
Case 2. \(\Upsilon(T_1)=\Upsilon(\mathit{T})-1\).
In this case, we have \(\alpha=2\); otherwise, \(u_2\) belongs to each minimum dominating set, which implies \(\Upsilon(\mathit{T}_1)=\Upsilon(\mathit{T})\). If \(\beta=n-\Upsilon\), then \(\mathit{T}\cong \mathfrak{T}_{n,\Upsilon}\), and the theorem holds. Henceforth, assume that \(\beta\leq n-\Upsilon-1\). By Case 1, we may suppose that \[deg_T(y_i)\leq 2,\qquad 1 \leq i \leq \beta-2.\] If \(u_4\) is a pendent vertex or a support vertex with \(deg_T(u_4)=2\), then \(\mathit{T}\cong \mathfrak{T}_{n,\Upsilon}\). In all other cases, without loss of generality, let \[deg_T(y_1)=\cdots=deg_T(y_{\beta_1})=1,\] and \[deg_T(y_{\beta_1+1})=\cdots=deg_T(y_{\beta_1+\beta_2})=2,\] where \(\beta_1+\beta_2=\beta-2\).
Case 2.1. \(\beta_1\geq 2\).
Let \(\mathit{T}_2=\mathit{T}-\{y_1\}\). Then \[\Upsilon(\mathit{T}_2)=\Upsilon(\mathit{T}).\] Using induction and Lemmas 2.1 and 2.2, we have \[\begin{aligned} EU(\mathit{T}) &=EU(\mathit{T}_2)+\mathfrak{f}(\beta,1)+\mathfrak{f}(\beta,2) -\mathfrak{f}(\beta-1,2) +\mathfrak{f}(deg_T(u_4),\beta)\\ &\quad-\mathfrak{f}(deg_{T_2}(u_4),\beta-1) +(\beta_1-1)\left(\mathfrak{f}(\beta,1)-\mathfrak{f}(\beta-1,1)\right)\\ &\quad+\beta_2\left(\mathfrak{f}(\beta,2)-\mathfrak{f}(\beta-1,2)\right)\\ &\leq \mathfrak{h}(n-1,\Upsilon)+\sqrt{\beta^2+1+\beta} +(\beta_1-1)\left(\sqrt{\beta^2+1+\beta} -\sqrt{(\beta-1)^2+1+(\beta-1)}\right)\\ &\quad+(\beta-\beta_1)\left(\sqrt{\beta^2+4+2\beta} -\sqrt{(\beta-1)^2+4+2(\beta-1)}\right). \end{aligned}\]
It is clear that \(\Upsilon\leq \frac{n-(\beta_1-1)}{2}\), i.e., \[\beta_1\leq n-2\Upsilon+1.\] Also, since \(\beta\leq n-\Upsilon-1\), using Lemmas 2.1 and 2.2, we have \[\begin{aligned} EU(\mathit{T}) &\leq \mathfrak{h}(n,\Upsilon) -(n-2\Upsilon+1)\left(\sqrt{(n-\Upsilon)^2+1+(n-\Upsilon)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\right)\\ &\quad-(\Upsilon-1)\left(\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)}\right)\\ &\quad-\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)} +\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\\ &\quad+(n-2\Upsilon)\left(\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-2)^2+1+(n-\Upsilon-2)}\right)\\ &\quad+(\Upsilon-2)\left(\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-2)^2+4+2(n-\Upsilon-2)}\right)\\ &=\mathfrak{h}(n,\Upsilon) +(n-2\Upsilon+1)\Big[ \left(\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-2)^2+1+(n-\Upsilon-2)}\right) -\left(\sqrt{(n-\Upsilon)^2+1+(n-\Upsilon)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\right)\Big]\\ &\quad+\left(\sqrt{(n-\Upsilon-2)^2+1+(n-\Upsilon-2)} -\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\right)\\ &\quad+\left(\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)} -\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)}\right)\\ &\quad+(\Upsilon-2)\Big[ \left(\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-2)^2+4+2(n-\Upsilon-2)}\right)\\ &\quad-\left(\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)} -\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)}\right)\Big]\\ &=\mathfrak{h}(n,\Upsilon) +(n-2\Upsilon+1)[\psi_1(n-\Upsilon-1)-\psi_1(n-\Upsilon)]\\ &\quad+\left(\sqrt{(n-\Upsilon-2)^2+1+(n-\Upsilon-2)} -\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\right)\\ &\quad+\left(\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)} -\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)}\right)\\ &\quad+(\Upsilon-2)[\psi_2(n-\Upsilon-1)-\psi_2(n-\Upsilon)] <\mathfrak{h}(n,\Upsilon). \end{aligned}\]
Case 2.2. \(\beta_1\leq 1\).
Let \[\mathit{T}_3=T-\{u_1,u_2\}.\] Then \[\mathit{T}_3\in\mathbb{T}_{n-2,\Upsilon-1}.\] Using induction and Lemmas 2.1 and 2.2, we have \[\begin{aligned} EU(\mathit{T}) &=EU(\mathit{T}_3)+\mathfrak{f}(\beta,deg_T(u_4)) -\mathfrak{f}(\beta-1,deg_{T_3}(u_4))\\ &\quad+\mathfrak{f}(\beta,deg_T(y_1)) -\mathfrak{f}(\beta-1,deg_{T_3}(y_1))\\ &\quad+(\beta-3)(\mathfrak{f}(\beta,2)-\mathfrak{f}(\beta-1,2)) +\mathfrak{f}(\beta,2)+\mathfrak{f}(1,2)\\ &\leq \mathfrak{h}(n-2,\Upsilon-1) +(\beta-2)\left(\sqrt{\beta^2+4+2\beta} -\sqrt{(\beta-1)^2+4+2(\beta-1)}\right)\\ &\quad+\sqrt{\beta^2+1+\beta} -\sqrt{(\beta-1)^2+1+(\beta-1)} +\sqrt{\beta^2+4+2\beta}+\sqrt{7}\\ &\leq \mathfrak{h}(n,\Upsilon) -(n-2\Upsilon+1)\left(\sqrt{(n-\Upsilon)^2+1+(n-\Upsilon)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\right)\\ &\quad-(\Upsilon-2)\left(\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)}\right)\\ &\quad-\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)}-\sqrt{7}\\ &\quad+(n-\Upsilon-3)\left(\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-2)^2+4+2(n-\Upsilon-2)}\right)\\ &\quad+\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)} -\sqrt{(n-\Upsilon-2)^2+1+(n-\Upsilon-2)}\\ &\quad+\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)}+\sqrt{7}\\ &=\mathfrak{h}(n,\Upsilon) +(n-2\Upsilon)\Big[ \left(\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)} -\sqrt{(n-\Upsilon)^2+1+(n-\Upsilon)}\right)\\ &\quad-\left(\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)} -\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\right)\Big]\\ &\quad+2\left(\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)} -\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)}\right)\\ &\quad+\Big[ \left(\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)} -\sqrt{(n-\Upsilon-2)^2+1+(n-\Upsilon-2)}\right)\\ &\quad-\left(\sqrt{(n-\Upsilon)^2+1+(n-\Upsilon)} -\sqrt{(n-\Upsilon-1)^2+1+(n-\Upsilon-1)}\right)\Big]\\ &\quad+(n-\Upsilon-3)\Big[ \left(\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)}\right.\\ &\quad\left.-\sqrt{(n-\Upsilon-2)^2+4+2(n-\Upsilon-2)}\right)\\ &\quad-\left(\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)} -\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)}\right)\Big]\\ &=\mathfrak{h}(n,\Upsilon) +(n-2\Upsilon)[\phi_1(n-\Upsilon)-\phi_1(n-\Upsilon-1)]\\ &\quad+2\left(\sqrt{(n-\Upsilon-1)^2+4+2(n-\Upsilon-1)} -\sqrt{(n-\Upsilon)^2+4+2(n-\Upsilon)}\right)\\ &\quad+[\psi_1(n-\Upsilon-1)-\psi_1(n-\Upsilon)] +(n-\Upsilon-3)[\psi_2(n-\Upsilon-1)-\psi_2(n-\Upsilon)]\\ &<\mathfrak{h}(n,\Upsilon), \end{aligned}\] since \(\beta\leq n-\Upsilon-1\) and \(n-\Upsilon-3\geq \beta-2\geq 0\). ◻
Let \(\mathscr{T}_{n,\beta}\) be the family of trees of order \(n\) with independence number \(\beta\). Let \(S_{n,\beta}\) be the tree obtained from the star \(K_{1,\beta}\) by attaching a pendent edge to each of its \(n-\beta-1\) pendent vertices. If \(\Delta=\beta\) in \(T\in \mathscr{T}_{n,\beta}\), then \(T\cong S_{n,\beta}\). We have \[EU(S_{n,\beta})=(2\beta-n+1)\sqrt{\beta^2+1+\beta} +(n-\beta-1)\sqrt{\beta^2+4+2\beta} +(n-\beta-1)\sqrt{7}.\]
Lemma 4.1. [22] Let \(T\) be a tree. If \(S(T)\) is a largest independent set in \(T\), then there exists at least one pendent vertex in \(S(T)\).
Theorem 4.2. Let \(T\in \mathscr{T}_{n,\beta}\). Then \[\label{EQ1} EU(T)\leq (2\beta-n+1)\sqrt{\beta^2+1+\beta} +(n-\beta-1)\sqrt{\beta^2+4+2\beta} +(n-\beta-1)\sqrt{7}, \tag{1}\] with equality if and only if \(T\cong S_{n,\beta}\).
Proof. Let \(\Delta\) denote the maximum degree in the tree \(T\), and let \(S(T)\) be a largest independent set in \(T\). Then \[|S(T)|=\beta(T)\geq \Delta.\] Using Lemma 4.1, we assume that \(u_1\) is a pendent vertex in \(S(T)\) and that \(u_2\) is its unique neighbor in \(T\). We have \(n\geq \beta+1\). If \(n=\beta+1\), then \(T\cong K_{1,n-1}\), and equality holds in (1). Similarly, if \(\Delta=\beta\), then \(T\cong S_{n,\beta}\), and equality again holds in (1). Otherwise, \[deg_T(u_i)\leq \Delta\leq \beta-1\] for every vertex \(u_i\in V(T)\). Let \[\eta=deg_T(u_2)^2+deg_T(u_j)^2+deg_T(u_2)deg_T(u_j)\] and \[\mu=(deg_T(u_2)-1)^2+deg_T(u_j)^2+(deg_T(u_2)-1)deg_T(u_j).\] Since \(deg_T(u_1)=1\), we derive \[\begin{aligned} \sum_{u_j:u_2u_j\in E(T)} &\left[\sqrt{\eta}-\sqrt{\mu}\right] +\sqrt{(deg_T(u_2)-1)^2+1+(deg_T(u_2)-1)}\\ &= \sum_{\substack{u_j:u_2u_j\in E(T)\\ j\neq 1}} \left[ \frac{2deg_T(u_2)-1+deg_T(u_j)}{\sqrt{\eta}+\sqrt{\mu}} \right] +\sqrt{deg_T(u_2)^2+1+deg_T(u_2)}\\ &<deg_T(u_2)-1+\sqrt{deg_T(u_2)^2+1+deg_T(u_2)} \leq 2d_T(u_2)\leq 2(\beta-1). \end{aligned}\]
We proceed by induction on \(n\). Assume that Eq. (1) is true for a positive integer \(n-1\). We show that it remains true when \(n\) is replaced by \(n+1\).
Since \(u_1\in S(T)\), let \[T^*=T-\{u_1\}.\] Then \[\beta(T^*)=\beta(T)-1.\] By the induction hypothesis, we have \[\begin{aligned} \label{EQ2} EU(T) =&EU(T^*)+ \sum_{u_j:u_2u_j\in E(T)} \bigg[ \sqrt{deg_T(u_2)^2+deg_T(u_j)^2+deg_T(u_2)deg_T(u_j)} \nonumber\\ &\quad-\sqrt{(deg_T(u_2)-1)^2+deg_T(u_j)^2+(deg_T(u_2)-1)deg_T(u_j)} \bigg]\nonumber\\ &+\sqrt{(deg_T(u_2)-1)^2+1+(deg_T(u_2)-1)} \nonumber\\ <&(2\beta-n)\sqrt{(\beta-1)^2+1+(\beta-1)} \nonumber\\ &+(n-\beta-1)\sqrt{(\beta-1)^2+4+2(\beta-1)} \nonumber\\ &+(n-\beta-1)\sqrt{7}+2(\beta-1). \end{aligned} \tag{2}\]
Since \(\beta\geq \Delta+1\) and \(T\) is a tree, we have \(3\leq \beta\) and \(\beta\geq n/2\). Using this, we derive \[\begin{aligned} &(2\beta-n+1)\sqrt{\beta^2+1+\beta} +(n-\beta-1)\sqrt{\beta^2+4+2\beta}\\ &\quad-(2\beta-n)\sqrt{(\beta-1)^2+1+(\beta-1)} -(n-\beta-1)\sqrt{(\beta-1)^2+4+2(\beta-1)} -2(\beta-1)\\ &=(2\beta-n)\left[\sqrt{\beta^2+1+\beta} -\sqrt{(\beta-1)^2+1+(\beta-1)}\right]\\ &\quad+(n-\beta-1)\left[\sqrt{\beta^2+4+2\beta} -\sqrt{(\beta-1)^2+4+2(\beta-1)}\right]\\ &\quad-2(\beta-1)+\sqrt{\beta^2+1+\beta}\\ &>\frac{(2\beta-n)(2\beta)}{\sqrt{\beta^2+1+\beta} +\sqrt{(\beta-1)^2+1+(\beta-1)}}\\ &\quad+\frac{(n-\beta-1)(2\beta+1)} {\sqrt{\beta^2+4+2\beta} +\sqrt{(\beta-1)^2+4+2(\beta-1)}} -(\beta-2)\\ &>\frac{2\beta(\beta-1)+n-\beta-1} {\sqrt{\beta^2+4+2\beta} +\sqrt{(\beta-1)^2+4+2(\beta-1)}} -(\beta-2)>0. \end{aligned}\]
Combining the above result with (2), we get \[EU(T)< (2\beta-n+1)\sqrt{\beta^2+1+\beta} +(n-\beta-1)\sqrt{\beta^2+4+2\beta} +(n-\beta-1)\sqrt{7}=EU(S_{n,\beta}).\] Thus, by induction, the inequality (1) holds strictly in the non-extremal case. This completes the proof. ◻
In this paper, we determined the lower and upper bounds of the Euler Sombor index for trees with a given domination number. Furthermore, we determined the upper bound of the Euler Sombor index for trees with a given independence number. We also characterized the corresponding extremal graphs.
Here we propose the following open problems.
Problem 5.1. Characterize extremal graphs for the Euler Sombor index of unicyclic and bicyclic graphs with a given domination number.
Problem 5.2. Characterize the minimum Euler Sombor index among all trees with a given independence number.
For a graph \(G\), the elliptic Sombor index \(ESO\) [13] is defined as \[ESO(G)=\sum_{uv \in E(G)} (deg_G^2(u)+deg_G^2(v)) \sqrt{deg_G^2(u)+deg_G^2(v)}.\]
Problem 5.3. Characterize extremal graphs for the elliptic Sombor index of trees with a given domination number.