The diminished Sombor index \(DSO(G)\) of a graph \(G\) is defined as \[DSO(G)=\sum_{uv\in E(G)}\frac{\sqrt{d_u^2+d_v^2}}{d_u+d_v},\] where \(d_u\) denotes the degree of vertex \(u\). Recently, this index has attracted considerable attention due to its promising chemical and mathematical properties. While the graphs minimizing the \(DSO\) index among various graph classes have been characterized, little is known about the next smallest values. In this paper, we extend these investigations by determining the extremal graphs that achieve the second through sixth minimum \(DSO\) indices. Specifically, for \(n\)-vertex trees, we identify all trees attaining the second to sixth smallest \(DSO\) values; for \(n\)-vertex unicyclic graphs, we characterize those with the second to sixth smallest \(DSO\) indices; and for \(n\)-vertex bicyclic graphs, we determine the graphs corresponding to the second to fifth smallest \(DSO\) indices. Our results provide a finer ordering of graphs by the diminished Sombor index and contribute to the systematic understanding of its extremal behavior.
Let \(G = (V(G), E(G))\) be a simple, undirected, connected graph with vertex set \(V(G)\) and edge set \(E(G)\). For a vertex \(u \in V(G)\), let \(d_u\) denote its degree. The maximum degree of \(G\) is denoted by \(\Delta\). The order and size of \(G\) are \(|V(G)|\) and \(|E(G)|\), respectively. A connected graph \(G\) is called a tree, a unicyclic graph, or a bicyclic graph if \(|E(G)| = |V(G)| – 1\), \(|E(G)| = |V(G)|\), or \(|E(G)| = |V(G)| + 1\), respectively.
Topological indices play a crucial role in mathematical chemistry and chemoinformatics by providing numerical descriptors that capture the structural features of molecular graphs without relying on three-dimensional geometry. Their primary significance lies in enabling quantitative structure-property relationship (QSPR) and quantitative structure activity relationship (QSAR) studies, where they serve as efficient molecular descriptors for predicting various physicochemical properties, biological activities, and toxicological endpoints of chemical compounds. By conducing complex molecular architectures into invariant numerical forms, topological indices facilitate rapid screening of large compound libraries, reduce the need for costly and time-consuming experimental assays, and guide the rational design of novel drugs, functional materials, and environmentally safe chemicals. Moreover, their theoretical foundation deepens our understanding of how connectivity patterns influence molecular stability, reactivity, and intermolecular interactions, thereby bridging discrete mathematics with applied fields such as pharmaceutical chemistry, environmental toxicology, and nanoscience. Consequently, topological indices have become indispensable tools in modern cheminformatics and computational molecular design. To date, scholars have proposed a large number of topological indices, such as the Wiener index [1], Zagreb indices [2], Randić index [3], Balaban index [4], Hosoya index [5], Albertson index [6], ABC index [7], Sombor index [8], the geometric-arithmetic index [9] and so on.
In 2021, Rajathagiri [10] introduced the diminished Sombor index of a graph \(G\), denoted \(DSO(G)\), and defined it as \[DSO(G) = \sum_{uv \in E(G)} \frac{\sqrt{d_u^2 + d_v^2}}{d_u + d_v}.\]
This index attracted considerable attention. In 2025, Movahedi, Gutman, Redžepović, and Furtula [11] systematically investigated its mathematical and chemical properties, which stimulated further research in this direction. Subsequently, Alotaibi et al. [12] identified all graphs that minimize the \(DSO\) index over the class of molecular graphs of order \(n\) and cyclomatic number \(\ell\), under the condition \(n \ge 2(\ell – 1) \ge 4\).
Das, Harshini, and Elumalai [13] provided a complete characterization of the tricyclic graphs that minimize the diminished Sombor index, thereby correcting the extremal conjecture made for this class in the aforementioned work of Movahedi, Gutman, Redžepović, and Furtula. Movahedi [14] determined the unique tricyclic graph of a given order that maximizes the \(DSO\) index and further analyzed some of its structural properties. Moreover, Movahedi [15] established several sharp bounds for the \(DSO\) index in terms of classical topological indices such as the Zagreb, Albertson, Harmonic, Randić, and geometric arithmetic indices. Guo and Wang [16] determined the maximum value of the diminished Sombor index among all molecular trees of order \(n\) with a perfect matching and characterized all the corresponding extremal trees.
In this paper, we determine the \(n\)-vertex trees with the second to sixth minimum \(DSO\) indices, the \(n\)-vertex unicyclic graphs with the second to sixth minimum \(DSO\) indices, and the \(n\)-vertex bicyclic graphs with the second to fifth minimum \(DSO\) indices.
Let \(\mathcal{T}_n\), \(\mathcal{U}_n\), and \(\mathcal{B}_n\) denote the sets of trees, unicyclic graphs, and bicyclic graphs on \(n\) vertices, respectively. Recall that a pendant edge is an edge incident with a vertex of degree one, whereas a path \(u_{1}u_{2}\ldots u_{t}\) is called a pendant path at \(u_{1}\) if \(d_{u_{1}}\geq 3\), \(d_{u_{i}}=2\) for \(i=2,\ldots,t-1\), and \(d_{u_{t}}=1\).
Lemma 1. [11] If \(G\) is a connected graph, then for any edge \(uv\in E(G)\), \[\frac{\sqrt{2}}{2} \le \frac{\sqrt{d_{u}^{2}+d_{v}^{2}}}{d_{u}+d_{v}} < 1.\]
The left equality holds if and only if \(d_{u}=d_{v}\).
Lemma 2. [11] Let \(f(x, y)=\frac{\sqrt{x^{2}+y^{2}}}{x+y}\), then \(f(x, y)\) is a monotonously increasing function of \(x\) and a monotonously decreasing function of \(y\) for \(x>y\).
Lemma 3. Let \(k\) be the number of pendant paths in \(G\), then \[DSO(G)\geq \frac{\sqrt{2}}{2}|E(G)|+(\frac{\sqrt{5}}{3}+\frac{\sqrt{13}}{5}-\sqrt{2})k.\]
Proof. Let \(l_{i}\) be the length of the \(i\)-th pendant path, where \(i=1,2\ldots k\). By Lemma 2, for any \(uv\in E(G)\), \(f(d_{u}, d_{v})=\frac{\sqrt{d_{u}^{2}+{d_{v}^{2}}}}{d_{u}+d_{v}}\) is a monotonously increasing function of \(d_{v}\) for \(d_{u}\leq d_{v}\leq \Delta\). There is a pendant path for any \(l_{i}=1\), which contributes to \(DSO(G)\) at least \(\frac{\sqrt{10}}{4}>\frac{\sqrt{5}}{3}+\frac{\sqrt{13}}{5}-\frac{\sqrt{2}}{2}\). There is a pendant path for any \(l_{i}\geq2\), which contributes to \(DSO(G)\) at least \(\frac{\sqrt{13}}{5}+\frac{\sqrt{2}}{2}(l_{i}-2)+\frac{\sqrt{5}}{3}=\frac{\sqrt{2}}{2}l_{i}+\frac{\sqrt{5}}{3}+\frac{\sqrt{13}}{5}-\sqrt{2}.\) Therefore, a pendent path for any \(l_{i}\geq1\) contributes to \(DSO(G)\) at least \(\frac{\sqrt{2}}{2}l_{i}+\frac{\sqrt{5}}{3}+\frac{\sqrt{13}}{5}-\sqrt{2}\). Note that there are \(k\) pendant paths in \(G\), then \[\begin{aligned} DSO(G) &\geq \sum_{i=1}^{k}\left(\frac{\sqrt{2}}{2}l_{i}+\frac{\sqrt{5}}{3}+\frac{\sqrt{13}}{5}-\sqrt{2}\right)+\frac{\sqrt{2}}{2}\left(|E(G)|-\sum_{i=1}^{k}l_{i}\right)\\ &= \frac{\sqrt{2}}{2}|E(G)|+\left(\frac{\sqrt{5}}{3}+\frac{\sqrt{13}}{5}-\sqrt{2}\right)k. \end{aligned}\]
This completes the proof. \(\square\)
It follows from [11] that the path \(P_{n}\) is the unique tree with the minimum \(DSO\) index among the \(n\)-vertex trees. In this section, for \(n \ge 11\), we determine the \(n\)-vertex trees that attain the six smallest values of the \(DSO\) index.
Theorem 1. Let \(n\geq 11\), \(T_n\in \mathcal{T}_n\setminus \{T^{1}, \ldots, T^{6}\}\), where the graphs \(T^{1}=P_{n}\), and \(T^{2}, \ldots, T^{6}\) are depicted in Figure 1. Then \[\begin{aligned} DSO(P_{n}) &= DSO(T^{1}) < DSO(T^{2}) < DSO(T^{3}) < DSO(T^{4}) \\ &< DSO(T^{5}) < DSO(T^{6}) < DSO(T_n), \end{aligned}\] where \[\begin{aligned} DSO(T^{1}) &= \frac{\sqrt{2}}{2}n+\frac{2\sqrt{5}}{3}-\frac{3\sqrt{2}}{2}, \\ DSO(T^{2}) &= \frac{\sqrt{2}}{2}n + \sqrt{5} + \frac{3\sqrt{13}}{5} – \frac{7\sqrt{2}}{2}, \\ DSO(T^{3}) &= \frac{\sqrt{2}}{2}n + \frac{\sqrt{10}}{4} + \frac{2\sqrt{13}}{5} + \frac{2\sqrt{5}}{3} – 3\sqrt{2}, \\ DSO(T^{4}) &= \frac{\sqrt{2}}{2}n + \frac{4\sqrt{13}}{5} + \frac{4\sqrt{5}}{3} – \frac{9\sqrt{2}}{2}, \\ DSO(T^{5}) &= \frac{\sqrt{2}}{2}n + \frac{\sqrt{5}}{3} + \frac{\sqrt{13}}{5} + \frac{\sqrt{10}}{2} – \frac{5\sqrt{2}}{2}, \\ DSO(T^{6}) &= \frac{\sqrt{2}}{2}n + \frac{6\sqrt{13}}{5} + \frac{4\sqrt{5}}{3} – \frac{11\sqrt{2}}{2}. \end{aligned}\]
Proof. Let \(T_n\) be an \(n\)-vertex tree different from the path \(P_n\), where \(n\ge 7\), and \(k\) denote the number of pendant paths in \(T_{n}\) . Then \(T_n\) contains at least three pendant paths; that is \(k\ge 3\). We distinguish three cases according to the number \(k\) of pendant paths.
Case 1. \(k=3\). \(\Delta=3\).
In this case \(T_n\) has exactly one vertex of maximum degree \(3\); all other vertices have degree \(1\) or \(2\).
Subcase 1.1. The unique vertex of degree \(3\) is adjacent to two vertices of degree \(1\) and one vertex of degree \(2\), namely \(T^{5}\). If \(T_{n} \in T^{5}\), then \[\begin{aligned} DSO(T_{n}) &= 2\cdot\frac{\sqrt{3^2+1^2}}{3+1} + \frac{\sqrt{3^2+2^2}}{3+2} + \frac{\sqrt{2^2+1^2}}{2+1} + \frac{\sqrt{2}}{2}(n-5)\\ &= \frac{\sqrt{2}}{2}n + \frac{\sqrt{5}}{3} + \frac{\sqrt{13}}{5} + \frac{\sqrt{10}}{2} – \frac{5\sqrt{2}}{2}. \end{aligned}\]
Subcase 1.2. The unique vertex of degree \(3\) is adjacent to one vertex of degree \(1\) and two vertices of degree \(2\), namely \(T^{3}\). If \(T_{n}\in T^{3}\), then \[\begin{aligned} DSO(T_{n}) &= 2\cdot\frac{\sqrt{3^2+2^2}}{3+2} + \frac{\sqrt{3^2+1^2}}{3+1} + 2\cdot\frac{\sqrt{2^2+1^2}}{2+1} + \frac{\sqrt{2}}{2}(n-6)\\ &= \frac{\sqrt{2}}{2}n + \frac{\sqrt{10}}{4} + \frac{2\sqrt{13}}{5} + \frac{2\sqrt{5}}{3} – 3\sqrt{2}. \end{aligned}\]
Subcase 1.3. The unique vertex of degree \(3\) is adjacent to three vertices of degree \(2\), namely \(T^{2}\). If \(T_{n}\in T^{2}\), then \[\begin{aligned} DSO(T_{n}) &= 3\cdot\frac{\sqrt{3^2+2^2}}{3+2} + 3\cdot\frac{\sqrt{2^2+1^2}}{2+1} + \frac{\sqrt{2}}{2}(n-7)\\ &= \frac{\sqrt{2}}{2}n + \sqrt{5} + \frac{3\sqrt{13}}{5} – \frac{7\sqrt{2}}{2}. \end{aligned}\]
Case 2. \(k=4\). We consider two cases:
Subcase 2.1. \(\Delta=4\). \(T_n\) contains exactly one vertex of degree \(4\) and all other vertices have degree \(1\) or \(2\). Using the inequality \[\frac{\sqrt{4^2+1^2}}{4+1} + \frac{\sqrt{2^2+2^2}}{2+2} > \frac{\sqrt{2^2+4^2}}{2+4} + \frac{\sqrt{2^2+1^2}}{2+1},\] we obtain \[\begin{aligned} DSO(T_n) &\ge 4\left(\frac{\sqrt{4^2+2^2}}{4+2} + \frac{\sqrt{2^2+1^2}}{2+1}\right) + \frac{\sqrt{2}}{2}(n-9)\\ &= \frac{\sqrt{2}}{2}n + \frac{8\sqrt{5}}{3} – \frac{9\sqrt{2}}{2}. \end{aligned}\]
Subcase 2.2. \(\Delta=3\). \(T_n\) contains exactly two vertices of degree \(3\) (and no vertex of higher degree). Denote \(d_{u}=d_{v}=3\). Note that \[\frac{\sqrt{1^2+3^2}}{1+3} + \frac{\sqrt{2^2+2^2}}{2+2} > \frac{\sqrt{3^2+2^2}}{3+2} + \frac{\sqrt{2^2+1^2}}{2+1}.\]
Subcase 2.2.1. Suppose \(T_n\) has at least one pendant path of length one. Then \[\begin{aligned} DSO(T_n) &\ge 3\left(\frac{\sqrt{2^2+3^2}}{2+3} + \frac{\sqrt{2^2+1^2}}{2+1}\right) + \frac{\sqrt{3^2+1^2}}{3+1} + \frac{\sqrt{2}}{2}(n-8)\\ &= \frac{\sqrt{2}}{2}n + \sqrt{5} + \frac{\sqrt{10}}{4} + \frac{3\sqrt{13}}{5} – 4\sqrt{2}. \end{aligned}\]
Subcase 2.2.2. Suppose all four pendant paths of \(T_n\) have length at least two. We distinguish whether \(u\) and \(v\) are adjacent.
If \(uv\in E(T_n)\), \(n\ge 10\), namely \(T^{4}\). If \(T_{n}\in T^{4}\), then \[DSO(T_{n})= 4\left(\frac{\sqrt{3^2+2^2}}{3+2} + \frac{\sqrt{2^2+1^2}}{2+1}\right) + \frac{\sqrt{2}}{2}(n-9) = \frac{\sqrt{2}}{2}n + \frac{4\sqrt{13}}{5} + \frac{4\sqrt{5}}{3} – \frac{9\sqrt{2}}{2}.\]
If \(uv\notin E(T_n)\), \(n\ge 11\) namely \(T^{6}\). If \(T_{n}\in T^{6}\), then \[DSO(T_{n})= 6\cdot\frac{\sqrt{3^2+2^2}}{3+2} + 4\cdot\frac{\sqrt{2^2+1^2}}{2+1} + \frac{\sqrt{2}}{2}(n-11) = \frac{\sqrt{2}}{2}n + \frac{6\sqrt{13}}{5} + \frac{4\sqrt{5}}{3} – \frac{11\sqrt{2}}{2}.\]
Case 3. \(k\ge 5\). By Lemma 3, we immediately obtain \[DSO(T_n) \ge \left(\frac{\sqrt{5}}{3} + \frac{\sqrt{13}}{5} – \sqrt{2}\right)k + \frac{\sqrt{2}}{2}(n-1) = \frac{\sqrt{2}}{2}n + \frac{5\sqrt{5}}{3} + \sqrt{13} – \frac{11\sqrt{2}}{2}.\]
Comparing the expressions obtained in all cases with the values \(DSO(T^1), \dots, DSO(T^6)\) listed in the theorem, we conclude that for \(n\ge 11\) the ordering \[\begin{aligned} DSO(P_{n}) &= DSO(T^{1}) < DSO(T^{2}) < DSO(T^{3}) < DSO(T^{4}) \\ &< DSO(T^{5}) < DSO(T^{6}) < DSO(T_n), \end{aligned}\] holds for every \(T_n \in\mathcal{T}_n\setminus\{T^1,\dots,T^6\}\). This completes the proof. \(\square\)
It follows from [11] that the cycle \(C_{n}\) is the unique unicyclic graph with the minimum \(DSO\) index among the \(n\)-vertex unicyclic graphs. In this section, for \(n \ge 9\), we determine the \(n\)-vertex unicyclic graphs that attain the six smallest values of the \(DSO\) index.
Theorem 2. Let \(n\geq 9\), \(U_n \in \mathcal{U}_n \setminus \{U^{1}, \ldots, U^{6}\}\), where \(U^{1}=C_{n}\), and the graphs \(U^{2}, \ldots, U^{6}\) are depicted in Figure 2. Then \[\begin{aligned} DSO(C_{n})& =DSO(U^{1})<DSO(U^{2})<DSO(U^{3})\\ & <DSO(U^{4})<DSO(U^{5})<DSO(U^{6})<DSO(U_{n}), \end{aligned}\] where \[\begin{aligned} DSO(U^{1}) &=\frac{\sqrt{2}}{2}n, \\ DSO(U^{2}) &= \frac{\sqrt{2}}{2}n + \frac{\sqrt{5}}{3} + \frac{3\sqrt{13}}{5} – 2\sqrt{2}, \\ DSO(U^{3}) &= \frac{\sqrt{2}}{2}n + \frac{\sqrt{10}}{4} + \frac{2\sqrt{13}}{5} – \frac{3\sqrt{2}}{2}, \\ DSO(U^{4}) &= \frac{\sqrt{2}}{2}n + \frac{4\sqrt{13}}{5} + \frac{2\sqrt{5}}{3} – 3\sqrt{2}, \\ DSO(U^{5}) &= \frac{\sqrt{2}}{2}n + \frac{3\sqrt{13}}{5} + \sqrt{5} – 3\sqrt{2}, \\ DSO(U^{6}) &= \frac{\sqrt{2}}{2}n + \frac{6\sqrt{13}}{5} + \frac{2\sqrt{5}}{3} – 4\sqrt{2}. \end{aligned}\]
Proof. Let \(U_{n}\) be an \(n\)-vertex unicyclic graph, where \(n\ge 3\), and \(k\) denote the number of pendant paths in \(U_{n}\). We distinguish several cases according to the value of \(k\).
Case 1. \(k=0\). Then \(U_{n}\) is the cycle \(C_n\), and \[DSO(C_{n})=\frac{\sqrt{2}}{2}n.\]
Case 2. \(k=1\). \(\Delta=3\). In this case \(U_{n}\) has exactly one vertex of maximum degree \(3\); all other vertices have degree \(1\) or \(2\).
Subcase 2.1. The unique vertex of degree \(3\) is adjacent to three vertices of degree \(2\), \(n\ge 5\), namely \(U^{2}\). If \(U_{n}\in U^{2}\), then \[\begin{aligned} DSO(U_n)&= 3\cdot\frac{\sqrt{3^2+2^2}}{3+2} + \frac{\sqrt{2^2+1^2}}{2+1} + \frac{\sqrt{2}}{2}(n-4)\\ &= \frac{\sqrt{2}}{2}n + \frac{\sqrt{5}}{3} + \frac{3\sqrt{13}}{5} – 2\sqrt{2}. \end{aligned}\]
Subcase 2.2. The unique vertex of degree \(3\) is adjacent to one vertex of degree \(1\) and two vertices of degree \(2\), \(n\ge 4\), namely \(U^{3}\). If \(U_{n}\in U^{3}\), Then \[\begin{aligned} DSO(U_{n}) &= 2\cdot\frac{\sqrt{3^2+2^2}}{3+2} + \frac{\sqrt{3^2+1^2}}{3+1} + \frac{\sqrt{2}}{2}(n-3)\\ &= \frac{\sqrt{2}}{2}n + \frac{\sqrt{10}}{4} + \frac{2\sqrt{13}}{5} – \frac{3\sqrt{2}}{2}. \end{aligned}\]
Case 3. \(k=2\). We consider two cases:
Subcase 3.1 \(\Delta=4\). \(U_{n}\) contains exactly one vertex of degree \(4\) on the cycle, and all other vertices have degree \(1\) or \(2\). We have \[\begin{aligned} DSO(U_{n}) &\ge 2\left(\frac{\sqrt{4^2+2^2}}{4+2} + \frac{\sqrt{2^2+1^2}}{2+1}\right) + 2\cdot\frac{\sqrt{4^2+2^2}}{4+2} + \frac{\sqrt{2}}{2}(n-6)\\ &= \frac{\sqrt{2}}{2}n + 2\sqrt{5} – 3\sqrt{2}. \end{aligned}\]
Subcase 3.2. \(\Delta=3\). \(U_{n}\) contains exactly two vertices of degree \(3\) (and no vertex of higher degree). Denote \(d_{u}=d_{v}=3\).
Subcase 3.2.1. Both pendant paths have length one. Then \[DSO(U_{n}) \ge 2\cdot\frac{\sqrt{3^2+1^2}}{3+1} + \frac{\sqrt{2}}{2}(n-2) = \frac{\sqrt{2}}{2}n + \frac{\sqrt{10}}{2} – \sqrt{2}.\]
Subcase 3.2.2. Exactly one pendant path has length one. Then there are at least three edges connecting vertices of degree \(2\) and \(3\). Hence \[\begin{aligned} DSO(U_{n}) &\ge 3\cdot\frac{\sqrt{3^2+2^2}}{3+2} + \frac{\sqrt{2^2+1^2}}{2+1} + \frac{\sqrt{3^2+1^2}}{3+1} + \frac{\sqrt{2}}{2}(n-5)\\ &= \frac{\sqrt{2}}{2}n + \frac{\sqrt{10}}{4} + \frac{\sqrt{5}}{3} + \frac{3\sqrt{13}}{5} – \frac{5\sqrt{2}}{2}. \end{aligned}\]
Subcase 3.2.3. Both pendant paths have length at least two. We distinguish whether \(u\) and \(v\) are adjacent.
If \(uv\in E(U_{n})\), namely \(U^{4}\). If \(U_{n}\in U^{4}\), then \[DSO(U_{n}) = 4\cdot\frac{\sqrt{3^2+2^2}}{3+2} + 2\cdot\frac{\sqrt{2^2+1^2}}{2+1} + \frac{\sqrt{3^2+3^2}}{3+3} + \frac{\sqrt{2}}{2}(n-7) = \frac{\sqrt{2}}{2}n + \frac{4\sqrt{13}}{5} + \frac{2\sqrt{5}}{3} – 3\sqrt{2}.\]
If \(uv\notin E(U_{n})\), namely \(U^{6}\). If \(U_{n}\in U^{6}\), then \[DSO(U_{n}) = 6\cdot\frac{\sqrt{3^2+2^2}}{3+2} + 2\cdot\frac{\sqrt{2^2+1^2}}{2+1} + \frac{\sqrt{2}}{2}(n-8) = \frac{\sqrt{2}}{2}n + \frac{6\sqrt{13}}{5} + \frac{2\sqrt{5}}{3} – 4\sqrt{2}.\]
Case 4. \(k=3\). We consider two subcases.
Subcase 4.1. There is at least one pendant path of length one. Then \[\begin{aligned} DSO(U_{n}) &\ge \frac{\sqrt{3^2+1^2}}{3+1} + 2\left(\frac{\sqrt{3^2+2^2}}{3+2} + \frac{\sqrt{2^2+1^2}}{2+1}\right) + \frac{\sqrt{2}}{2}(n-5)\\ &= \frac{\sqrt{2}}{2}n + \frac{\sqrt{10}}{4} + \frac{2\sqrt{13}}{5} + \frac{2\sqrt{5}}{3} – \frac{5\sqrt{2}}{2}. \end{aligned}\]
Subcase 4.2. No pendant path has length one. We further distinguish:
Subcase 4.2.1. There is a pendant path attached to a vertex of degree at least \(4\). Then \[\begin{aligned} DSO(U_{n}) &\ge \frac{\sqrt{4^2+2^2}}{4+2} + \frac{\sqrt{2^2+1^2}}{2+1} + 2\left(\frac{\sqrt{3^2+2^2}}{3+2} + \frac{\sqrt{2^2+1^2}}{2+1}\right) + \frac{\sqrt{2}}{2}(n-6)\\ &= \frac{\sqrt{2}}{2}n + \frac{2\sqrt{13}}{5} + \frac{4\sqrt{5}}{3} – 3\sqrt{2}. \end{aligned}\]
Subcase 4.2.2. \(\Delta=3\). Assume that the three pendant paths emanate from three vertices \(x\), \(y\), \(z\) (which are the vertices of degree \(3\) on the cycle).
Subcase 4.2.2.1. At most two of the pairs \(\{x,y\}\), \(\{y,z\}\), \(\{z,x\}\) are adjacent. Then there are at least five edges connecting vertices of degree \(2\) and \(3\). Since there are three pendant edges, we obtain \[DSO(U_{n}) \ge 5\cdot\frac{\sqrt{3^2+2^2}}{3+2} + 3\cdot\frac{\sqrt{2^2+1^2}}{2+1} + \frac{\sqrt{2}}{2}(n-8) = \frac{\sqrt{2}}{2}n + \sqrt{13} + \sqrt{5} – 4\sqrt{2}.\]
Subcase 4.2.2.2. The vertices \(x\), \(y\), \(z\) are pairwise adjacent (i.e., they form a triangle). The graph is obtained by attaching a path of length at least two to each vertex of the triangle, namely \(U^{5}\). If \(U_{n}\in U^{5}\), then \[DSO(U_{n}) = 3\cdot\frac{\sqrt{3^2+2^2}}{3+2} + 3\cdot\frac{\sqrt{3^2+3^2}}{3+3} + 3\cdot\frac{\sqrt{2^2+1^2}}{2+1} + \frac{\sqrt{2}}{2}(n-9) = \frac{\sqrt{2}}{2}n + \frac{3\sqrt{13}}{5} + \sqrt{5} – 3\sqrt{2}.\]
Case 5. \(k\ge 4\). By Lemma 3, we have \[\begin{aligned} DSO(U_{n}) &\ge \frac{\sqrt{2}}{2}n + \left(\frac{\sqrt{5}}{3} + \frac{\sqrt{13}}{5} – \sqrt{2}\right)k \\ &\ge \frac{\sqrt{2}}{2}n + 4\left(\frac{\sqrt{5}}{3} + \frac{\sqrt{13}}{5} – \sqrt{2}\right) \\ &= \frac{\sqrt{2}}{2}n + \frac{4\sqrt{5}}{3} + \frac{4\sqrt{13}}{5} – 4\sqrt{2}. \end{aligned}\]
Comparing the expressions obtained in all cases with the values \(DSO(U^1),\dots,DSO(U^6)\) listed in the theorem, we conclude that for \(n\ge 9\) the ordering \[\begin{aligned} DSO(C_{n})& =DSO(U^{1})<DSO(U^{2})<DSO(U^{3})\\ & <DSO(U^{4})<DSO(U^{5})<DSO(U^{6})<DSO(U_{n}), \end{aligned}\] holds for every \(U_n\in\mathcal{U}_n\setminus\{U^1,\dots,U^6\}\). This completes the proof. \(\square\)
For convenience, we introduce the following notation for certain classes of bicyclic graphs:
\(B_{1}^{1}\): the class of bicyclic graphs of order \(n\) obtained by adding an edge to an \(n\)-cycle \(C_{n}\), where \(n\ge 4\).
\(B_{2}^{1}\): the class of bicyclic graphs of order \(n\) obtained by connecting two disjoint cycles \(C_{a}\) and \(C_{b}\) (with \(a+b=n\)) by a single edge, where \(n\ge 6\).
\(B^{2}\): the class of bicyclic graphs of order \(n\) obtained from a cycle \(C_{a}=v_{0}v_{1}\dots v_{a-1}\) (\(4\le a\le n-2\)) by adding an edge between \(v_{0}\) and \(v_{2}\), and attaching a path of \(n-a\) vertices to \(v_{1}\).
\(B_{1}^{3}\): the class of bicyclic graphs of order \(n\) obtained by connecting two non-adjacent vertices of a cycle \(C_{a}\) (\(4\le a\le n-1\)) with a path of length \(n-a+1\), where \(n\ge5\).
\(B_{2}^{3}\): the class of bicyclic graphs of order \(n\) obtained by connecting two disjoint cycles \(C_{a}\) and \(C_{b}\) (with \(a+b<n\)) with a path of length \(n-a-b+1\), where \(n\ge7\).
\(B^{4}\): the class of bicyclic graphs of order \(n\) obtained by attaching a path containing at least two vertices to each of the two vertices of degree \(2\) in the unique \(4\)-vertex bicyclic graph, where \(n\ge8\).
\(B_{1}^{5}\): the class of bicyclic graphs of order \(n\) obtained by attaching a path of \(n-k\ge2\) vertices to a vertex of degree \(2\) (whose two neighbors have degrees \(2\) and \(3\), respectively) in a graph from \(B_{1}^{1}(k)\) (\(k\ge5\)) or \(B_{1}^{2}(k)\) (\(k\ge6\)), where \(n\ge7\).
\(B_{2}^{5}\): the class of bicyclic graphs of order \(n\) obtained by attaching a path of \(n-k\ge2\) vertices to a vertex of degree \(2\) (whose two neighbors are both of degree \(3\)) in a graph from \(B_{3}^{1}(k)\) (\(k\ge5\)) or \(B_{3}^{2}(k)\) (\(k\ge7\)), where \(n\ge7\).
\(B^{6}\): the class of bicyclic graphs of order \(n\) (\(n\ge5\)) obtained by joining \(v_0\) and \(v_2\) of the cycle \(C_{n-1}=v_0v_1\cdots v_{n-2}\), and attaching a pendant vertex to \(v_1\).
It follows from [11] that the graphs in \(B_{1}^{1}\) (for \(n\ge4\)) and the graphs in \(B_{1}^{2}\) (for \(n\ge6\)) are the unique graphs attaining the minimum \(DSO\) index, and \[DSO(B_{1}^{1})=DSO(B_{2}^{1})=\frac{\sqrt{2}}{2}n+\frac{4\sqrt{13}}{5}-\frac{3\sqrt{2}}{2}.\]
Theorem 3. Let \(n \ge 9\) and \(B_n \in \mathcal{B}_n \setminus \{B_1^1, B_2^1, B^2, B_1^3, B_2^3, B^4, B_1^5, B_2^5\}\), where the graphs \(B_1^1, B_2^1, B^2, B_1^3, B_2^3, B^4, B_1^5, B_2^5\) are depicted in Figure 3. Then \[\begin{aligned} DSO(B_{1}^{1})&=DSO(B_{2}^{1})<DSO(B^{2})<DSO(B_{1}^{3})=DSO(B_{2}^{3})\\ & <DSO(B^{4})<DSO(B_{1}^{5})=DSO(B_{2}^{5})<DSO(B_n), \end{aligned}\] where \[\begin{aligned} DSO(B^2) &= \frac{\sqrt{2}}{2}\,n + \frac{3\sqrt{13}}{5} + \frac{\sqrt{5}}{3} – \frac{3\sqrt{2}}{2},\\[2mm] DSO(B_1^3)=DSO(B_2^3) &= \frac{\sqrt{2}}{2}\,n + \frac{6\sqrt{13}}{5} – \frac{5\sqrt{2}}{2},\\[2mm] DSO(B^4) &= \frac{\sqrt{2}}{2}\,n + \frac{2\sqrt{13}}{5} + \frac{2\sqrt{5}}{3} – \frac{3\sqrt{2}}{2},\\[2mm] DSO(B_1^5)=DSO(B_2^5) &= \frac{\sqrt{2}}{2}\,n + \frac{\sqrt{5}}{3} + \sqrt{13} – \frac{5\sqrt{2}}{2}. \end{aligned}\]
Proof. Let \(k\) denote the number of pendant vertices of \(B_{n}\). We consider four cases according to the value of \(k\).
Case 1. \(k = 0\). Then \(3 \le \Delta \le 4\). If \(B_{n} \in B_1^3\) (\(n \ge 5\)) or \(B_{n} \in B_2^3\) (\(n \ge 7\)), then
\[DSO(B_{n}) = \frac{\sqrt{3^2+2^2}}{3+2}\cdot 6 + \frac{\sqrt{2}}{2}(n-5) = \frac{\sqrt{2}}{2}\,n + \frac{6\sqrt{13}}{5} – \frac{5\sqrt{2}}{2}.\]
If \(B_{n}\) is obtained by identifying a common vertex of two cycles, then \[DSO(B_{n}) = \frac{\sqrt{4^2+2^2}}{4+2}\cdot 4 + \frac{\sqrt{2}}{2}(n-3) = \frac{\sqrt{2}}{2}\,n + \frac{4\sqrt{5}}{3} – \frac{3\sqrt{2}}{2}.\]
Case 2. \(k = 1\). Then \(3 \le \Delta \le 5\). We distinguish two subcases:
Subcase 2.1. the unique pendant path has length \(1\).
(1) \(\Delta = 4\) or \(5\). Then \(B_{n}\) contains at least two edges joining a vertex of degree \(2\) with a vertex of degree \(\Delta\). Hence \[\begin{aligned} DSO(B_{n}) &\ge \frac{\sqrt{\Delta^2+2^2}}{2+\Delta}\cdot 2 + \frac{\sqrt{3^2+1^2}}{3+1} + \frac{\sqrt{2}}{2}(n-2) \\ &\ge \frac{\sqrt{4^2+2^2}}{2+4}\cdot 2 + \frac{\sqrt{10}}{4} + \frac{\sqrt{2}}{2}(n-2) \\ &= \frac{\sqrt{2}}{2}\,n + \frac{2\sqrt{5}}{3} + \frac{\sqrt{10}}{4} – \sqrt{2} \end{aligned}\]
(2) \(\Delta =3\). Then \(B_{n}\) has exactly three vertices of degree \(3\), denoted \(x,y,z\).
If at most two pairs among \(\{x,y,z\}\) are adjacent, then there are at least four edges joining a vertex of degree \(2\) with a vertex of degree \(3\). Thus \[DSO(B_{n}) \ge \frac{\sqrt{3^2+2^2}}{3+2}\cdot 4 + \frac{\sqrt{3^2+1^2}}{3+1} + \frac{\sqrt{2}}{2}(n-4) = \frac{\sqrt{2}}{2}\,n + \frac{4\sqrt{13}}{5} + \frac{\sqrt{10}}{4} – 2\sqrt{2}.\]
If \(x,y,z\) are pairwise adjacent, then \(B_{n} \in B^6\) (\(n \ge 5\)) and \[DSO(B_{n}) = \frac{\sqrt{3^2+2^2}}{3+2}\cdot 2 + \frac{\sqrt{3^2+1^2}}{3+1} + \frac{\sqrt{2}}{2}(n-2) = \frac{\sqrt{2}}{2}\,n + \frac{2\sqrt{13}}{5} + \frac{\sqrt{10}}{4} – \sqrt{2}.\]
Subcase 2.2. it has length at least \(2\).
(1) \(\Delta = 4\) or \(5\). Then \(B_{n}\) contains at least three edges joining a vertex of degree \(2\) with a vertex of degree \(\Delta\). Consequently, \[\begin{aligned} DSO(B_{n}) &\ge \frac{\sqrt{2^2+\Delta^2}}{2+\Delta}\cdot 3 + \frac{\sqrt{2^2+1^2}}{2+1} + \frac{\sqrt{2}}{2}(n-3) \\ &\ge \frac{\sqrt{2^2+4^2}}{2+4}\cdot 3 + \frac{\sqrt{5}}{3} + \frac{\sqrt{2}}{2}(n-3) \\ &= \frac{\sqrt{2}}{2}\,n + \frac{4\sqrt{5}}{3} – \frac{3\sqrt{2}}{2}. \end{aligned}\]
(2) \(\Delta = 3\). Then \(B_{n}\) has exactly three vertices of degree \(3\), denoted \(x,y,z\).
If at most one pair among \(\{x,y,z\}\) is adjacent, then there are at least seven edges joining a vertex of degree \(2\) with a vertex of degree \(3\). Hence \[DSO(B_{n}) \ge \frac{\sqrt{3^2+2^2}}{3+2}\cdot 7 + \frac{\sqrt{2^2+1^2}}{2+1} + \frac{\sqrt{2}}{2}(n-7) = \frac{\sqrt{2}}{2}\,n + \frac{7\sqrt{13}}{5} + \frac{\sqrt{5}}{3} – \frac{7\sqrt{2}}{2}.\]
If exactly two pairs among \(\{x,y,z\}\) are adjacent, then \(B_{n} \in B_5^1(n)\) or \(B_{n} \in B_5^2(n)\) (\(n \ge 7\)), and \[DSO(B_{n}) = \frac{\sqrt{3^2+2^2}}{3+2}\cdot 5 + \frac{\sqrt{2^2+1^2}}{2+1} + \frac{\sqrt{2}}{2}(n-5) = \frac{\sqrt{2}}{2}\,n + \frac{\sqrt{5}}{3} + \sqrt{13} – \frac{5\sqrt{2}}{2}.\]
If \(x,y,z\) are pairwise adjacent, then \(B_{n} \in B^2\) (\(n \ge 6\)) and \[DSO(B_{n}) = \frac{\sqrt{3^2+2^2}}{3+2}\cdot 3 + \frac{\sqrt{2^2+1^2}}{2+1} + \frac{\sqrt{2}}{2}(n-3) = \frac{\sqrt{2}}{2}\,n + \frac{3\sqrt{13}}{5} + \frac{\sqrt{5}}{3} – \frac{3\sqrt{2}}{2}.\]
Case 3. \(k = 2\). Then \(3 \le \Delta \le 6\).
(1) \(4 \le \Delta \le 6\). There are at least two edges joining a vertex of degree \(2\) with a vertex of degree \(\Delta\). Moreover, there are two edges of the type \((2,1)\) and two of the type \((3,2)\) (from the two pendant paths). Hence \[\begin{aligned} DSO(B_{n}) &\ge \frac{\sqrt{2^2+\Delta^2}}{2+\Delta}\cdot 2 + \left(\frac{\sqrt{2^2+1^2}}{2+1}+\frac{\sqrt{3^2+2^2}}{3+2}\right)\!\cdot 2 + \frac{\sqrt{2}}{2}(n-5)\\ &\ge \frac{\sqrt{2^2+4^2}}{2+4}\cdot 2 + \left(\frac{\sqrt{5}}{3}+\frac{\sqrt{13}}{5}\right)\!\cdot 2 + \frac{\sqrt{2}}{2}(n-5)\\ &= \frac{\sqrt{2}}{2}\,n + \frac{4\sqrt{5}}{3} + \frac{3\sqrt{13}}{5} – \frac{5\sqrt{2}}{2}. \end{aligned}\]
(2) \(\Delta = 3\). Then \(B_{n}\) has exactly four vertices of degree \(3\), denoted \(x,y,z,w\).
If there exists a pendant path of length \(1\), then \[DSO(B_{n}) \ge \frac{\sqrt{3^2+1^2}}{3+1} + \frac{\sqrt{2^2+1^2}}{2+1} + \frac{\sqrt{3^2+2^2}}{3+2} + \frac{\sqrt{2}}{2}(n-2) = \frac{\sqrt{2}}{2}\,n + \frac{\sqrt{10}}{4} + \frac{\sqrt{13}}{5} – \sqrt{2}.\]
If all pendant paths have length at least \(2\) (by the structure of bicyclic graphs, at most five pairs among \(\{x,y,z,w\}\) can be adjacent):
If at most four pairs are adjacent, then there are at least four edges joining a vertex of degree \(2\) with a vertex of degree \(3\), and two edges of type \((2,1)\). Hence \[DSO(B_{n}) \ge \frac{\sqrt{3^2+2^2}}{3+2}\cdot 4 + \frac{\sqrt{2^2+1^2}}{2+1}\cdot 2 + \frac{\sqrt{2}}{2}(n-5) = \frac{\sqrt{2}}{2}\,n + \frac{4\sqrt{13}}{5} + \frac{2\sqrt{5}}{3} – \frac{5\sqrt{2}}{2}.\]
If exactly five pairs are adjacent, then \(B_{n} \in B^4\) (\(n \ge 8\)) and \[DSO(B_{n})= \frac{\sqrt{3^2+2^2}}{3+2}\cdot 2 + \frac{\sqrt{2^2+1^2}}{2+1}\cdot 2 + \frac{\sqrt{2}}{2}(n-3) = \frac{\sqrt{2}}{2}\,n + \frac{2\sqrt{13}}{5} + \frac{2\sqrt{5}}{3} – \frac{3\sqrt{2}}{2}.\]
Case 4. \(k \ge 3\). By Lemma 3, we obtain \[DSO(B_{n}) \ge \frac{\sqrt{2}}{2}(n+1) + \left(\frac{\sqrt{5}}{3}+\frac{\sqrt{13}}{5}-\sqrt{2}\right)\!\cdot 3 = \frac{\sqrt{2}}{2}\,n + \sqrt{5} + \frac{3\sqrt{13}}{5} – \frac{5\sqrt{2}}{2}.\]
Comparing the expressions obtained in the various cases with the explicit formulas listed in the theorem yields the desired chain of inequalities. This completes the proof. \(\square\)
Acknowledgments: We are grateful to a referee for many useful comments which improved this paper. This work is supported by National Natural Science Foundation of China (No. 12261074).
