Extremal \((n,m)\)-graphs with respect to VDB topological indices

1. Introduction

Let \(G\) be a simple connected graph with vertex set \(V(G)\) and edge set \(E(G)\). \(|V(G)|=n\) is the number of vertices, \(|E(G)|=m\) is the number of edges of \(G\). The set of graphs with \(|V(G)|=n\) and \(|E(G)|=m\) are called (n,m) graphs. Denote by \(N_{G}(u)\) the set of vertices which are neighbors of the vertex \(u\). Then \(|N_{G}(u)|\) is the degree of vertex \(u\), denoted by \(d_{u}\). Let \(\Delta(G)\), \(\delta(G)\) be the maximum degree, minimum degree of \(G\). For all notations and terminology used, but not defined here, we refer to the textbook [1].

Let \(f(x,y)\) be a symmetric real function, \(d(u)\) the degree of vertex \(u\) in \(G\). The vertex-degree based topological (or graphical function-index) \(TI_{f}(G)\) of \(G\) with edge-weight function \(f(x,y)\) was defined as [2] \begin{equation}\label{eq:11} TI_{f}(G)=\sum_{uv\in E(G)}f(d(u),d(v)). \end{equation}

There are several research on extremal VDB topological indices, see [3, 4, 5, 6, 7, 8, 9, 10]. Gutman [11] listed most of the VDB indices, we show in the Table 1.

If \(f(x,y)\) is monotonically increasing on \(x\) (or \(y\)), \(h(x)=f(a,x)-f(b,x)\) is monotonically decreasing on \(x\) for any \(a\geq b\geq 0\), then we call \(f(x,y)\) is the first good function.

If \(f(x,y)\) is monotonically decreasing on \(x\) (or \(y\)), \(h(x)=f(a,x)-f(b,x)\) is monotonically increasing on \(x\) for any \(a\geq b\geq 0\), then we call \(f(x,y)\) is the second good function.

The present paper was motivated by a recent paper of Aashtab et al., [12] on Sombor index, where they study the structure of a graph with minimum Sombor index among all graphs with fixed order and fixed size. They shown that in every graph with minimum Sombor index the difference between minimum and maximum degrees is at most 1. We take further the line of considering the extremal values of VDB topological indices of connected \((n,m)\)-graphs by a unified way. We obtain some properties of extremal connected \((n,m)\)-graphs with respect to VDB topological indices.

Table 1. VDB topological indices.

Function \(f(x,y)\)	Equation (1) corresponds to	Symbol
\(1/\sqrt{xy}\)	Randić index [13]	\(R\)
\(\sqrt{x^{2}+y^{2}}\)	Sombor index [11]	\(SO\)
\(\sqrt{x+y-2/xy}\)	atom-bond connectivity index [14]	\(ABC\)
\(x+y\)	first Zagreb index [15,16]	\(M_{1}\)
\(xy\)	second Zagreb index [17]	\(M_{2}\)
\(1/\sqrt{x+y}\)	sum-connectivity index [18]	\(\chi\)
\([xy/(x+y-2)]^{3}\)	augmented Zagreb index [19]	\(AZI\)
\(\sqrt{xy}\)	reciprocal Randić index [20]	\(RR\)
\(x^2+y^2\)	forgotten topological index [15]	\(F\)
\(2xy/(x+y)\)	inverse sum indeg index [21]	\(ISI\)
\(2/(x+y)\)	harmonic index [22]	\(H\)
\(2\sqrt{xy}/(x+y)\)	geometric-arithmetic index [23]	\(GA\)
\((x+y)/(2\sqrt{xy})\)	arithmetic-geometric index [24]	\(AG\)
\(1/x^2+1/y^2\)	inverse degree index [22]	\(ID\)
\(|x-y|\)	Albertson index [25]	\(Alb\)
\(y/x+x/y\)	symmetric division deg index [21]	\(SDD\)

2. Main Results

Theorem 1. Let \(G\) be a connected (n,m) graph and \(f(x,y)\) is the first good function. For any \(a>b+1\geq 2\), \(H(a,b)>0\), where \(H(a,b)=a[f(a,a)-f(a-1,a)]-b[f(b+1,b)-f(b,b)]\). If \(TI_{f}(G)\) has the minimum value in \(G\), then \(G\) is an almost regular graph, i.e., \(\Delta(G)-\delta(G) \leq 1\).

Proof. On the contrary, we suppose \(G\) is not an almost regular graph, i.e., \(\Delta(G)-\delta(G) \geq 2\). Let \(d(u)=\Delta\), \(d(v)=\delta\).

Case 1. \(uv\notin E(G)\).

Let \(N_{G}(u)=\{u_{1},u_{2},\cdots,u_{\Delta}\}\), \(N_{G}(v)=\{v_{1},v_{2},\cdots,v_{\delta}\}\). Since \(\Delta(G)-\delta(G) \geq 2\), we suppose \(u_{\Delta}\notin N_{G}(v)\). Let \(S\subseteq E(G)\) be the set of edges which adjacent to \(u\) or \(v\). Let \(G^{*}=G-uu_{\Delta}+vu_{\Delta}\). \begin{eqnarray*} TI_{f}(G) = \sum_{uv\in E(G)\setminus S}f(d(u),d(v))+\sum_{i=1}^{\Delta}f(\Delta,d(u_{i}))+\sum_{i=1}^{\delta}f(\delta,d(v_{i})). \end{eqnarray*} \begin{eqnarray*} TI_{f}(G^{*}) = \sum_{uv\in E(G)\setminus S}f(d(u),d(v))+\sum_{i=1}^{\Delta-1}f(\Delta-1,d(u_{i}))+\sum_{i=1}^{\delta}f(\delta+1,d(v_{i})) +f(d(u_{\Delta}),\delta+1). \end{eqnarray*} \begin{eqnarray*} TI_{f}(G)-TI_{f}(G^{*}) & = & \sum_{i=1}^{\Delta-1}[f(\Delta,d(u_{i}))-f(\Delta-1,d(u_{i}))] – \sum_{i=1}^{\delta}[f(\delta+1,d(v_{i}))-f(\delta,d(v_{i}))] \\ & & +f(\Delta,d(u_{\Delta}))-f(\delta+1,d(u_{\Delta}))\\ & = & \sum_{i=1}^{\Delta}[f(\Delta,d(u_{i}))-f(\Delta-1,d(u_{i}))] – \sum_{i=1}^{\delta}[f(\delta+1,d(v_{i}))-f(\delta,d(v_{i}))] \\ & & +f(\Delta-1,d(u_{\Delta}))-f(\delta+1,d(u_{\Delta}))\\ & \geq & \sum_{i=1}^{\Delta}[f(\Delta,d(u_{i}))-f(\Delta-1,d(u_{i}))] – \sum_{i=1}^{\delta}[f(\delta+1,d(v_{i}))-f(\delta,d(v_{i}))]\\ & \geq & \sum_{i=1}^{\Delta}[f(\Delta,\Delta)-f(\Delta-1,\Delta)] – \sum_{i=1}^{\delta}[f(\delta+1,\delta)-f(\delta,\delta)]\\ & = & \Delta[f(\Delta,\Delta)-f(\Delta-1,\Delta)]-\delta[f(\delta+1,\delta)-f(\delta,\delta)]>0. \end{eqnarray*}

Case 2. \(uv\in E(G)\).

Let \(N_{G}(u)=\{u_{1},u_{2},\cdots,u_{\Delta-1},v\}\), \(N_{G}(v)=\{v_{1},v_{2},\cdots,v_{\delta-1},u\}\). Since \(\Delta(G)-\delta(G) \geq 2\), we suppose \(u_{\Delta-1}\notin N_{G}(v)\). Let \(S\subseteq E(G)\) be the set of edges which adjacent to \(u\) or \(v\). Let \(G^{**}=G-uu_{\Delta-1}+vu_{\Delta-1}\). \begin{eqnarray*} TI_{f}(G) = \sum_{uv\in E(G)\setminus S}f(d(u),d(v))+\sum_{i=1}^{\Delta-1}f(\Delta,d(u_{i}))+\sum_{i=1}^{\delta-1}f(\delta,d(v_{i}))+f(\Delta,\delta). \end{eqnarray*} \begin{eqnarray*} TI_{f}(G^{**}) & = & \sum_{uv\in E(G)\setminus S}f(d(u),d(v))+\sum_{i=1}^{\Delta-2}f(\Delta-1,d(u_{i}))+\sum_{i=1}^{\delta-1}f(\delta+1,d(v_{i}))\\ & & +f(d(u_{\Delta-1}),\delta+1)+f(\Delta-1,\delta+1). \end{eqnarray*} \begin{eqnarray*} TI_{f}(G)-TI_{f}(G^{**}) & = & \sum_{i=1}^{\Delta-1}[f(\Delta,d(u_{i}))-f(\Delta-1,d(u_{i}))] – \sum_{i=1}^{\delta-1}[f(\delta+1,d(v_{i}))-f(\delta,d(v_{i}))] \\ & & +f(\Delta,\delta)-f(\Delta-1,\delta+1) +f(\Delta-1,d(u_{\Delta-1}))-f(\delta+1,d(u_{\Delta-1}))\\ & \geq & \sum_{i=1}^{\Delta-1}[f(\Delta,d(u_{i}))-f(\Delta-1,d(u_{i}))] – \sum_{i=1}^{\delta-1}[f(\delta+1,d(v_{i}))-f(\delta,d(v_{i}))] \\ & & +f(\Delta,\delta)-f(\Delta-1,\delta+1) \\ & \geq & (\Delta-1)[f(\Delta,\Delta)-f(\Delta-1,\Delta)]-(\delta-1)[f(\delta+1,\delta)-f(\delta,\delta)]\\ & & +f(\Delta,\delta)-f(\Delta-1,\delta+1), \end{eqnarray*} since \(\Delta[f(\Delta,\Delta)-f(\Delta-1,\Delta)]-\delta[f(\delta+1,\delta)-f(\delta,\delta)]>0\), then \(TI_{f}(G)-TI_{f}(G^{**}) > f(\Delta-1,\Delta)-f(\Delta,\Delta)+f(\delta+1,\delta)-f(\delta,\delta) +f(\Delta,\delta)-f(\Delta-1,\delta+1)\). Since \(f(x,y)\) is the first good function, \(h(x)=f(a,x)-f(b,x)\) is monotonically decreasing on \(x\) for any \(a\geq b\geq 0\). Then for any \(a_{1}\geq a_{2}\geq a_{3}\geq a_{4}\geq 0\), we have \(f(a_{1},a_{3})-f(a_{1},a_{2})\geq f(a_{3},a_{4})-f(a_{2},a_{4})\). Thus we have \(f(\Delta-1,\Delta)+f(\Delta,\delta)+f(\delta+1,\delta)\geq f(\Delta,\Delta) +f(\Delta-1,\delta)+f(\delta+1,\delta)\), and \(f(\Delta-1,\delta)+f(\delta+1,\delta)+f(\Delta,\Delta)\geq f(\delta,\delta) +f(\Delta-1,\delta+1)+f(\Delta,\Delta)\). We have \(TI_{f}(G)-TI_{f}(G^{**})> 0\), which is contradict with that \(TI_{f}(G)\) has the minimum value in \(G\), thus by Case 1 and Case 2, we know \(G\) is a almost regular graph, i.e., \(\Delta(G)-\delta(G) \leq 1\).

Similarly, we also have

Theorem 2. Let \(G\) be a connected (n,m) graph and \(f(x,y)\) is the second good function. For any \(a>b+1\geq 2\), \(H(a,b)< 0\), where \(H(a,b)=a[f(a,a)-f(a-1,a)]-b[f(b+1,b)-f(b,b)]\). If \(TI_{f}(G)\) has the maximum value in \(G\), then \(G\) is an almost regular graph, i.e., \(\Delta(G)-\delta(G) \leq 1\).

In the following, we suppose \(f(x,y)\) is the first good function, and for any \(a>b+1\geq 2\), \(H(a,b)>0\), where \(H(a,b)=a[f(a,a)-f(a-1,a)]-b[f(b+1,b)-f(b,b)]\). Similar to the Corollary 1-4 of [12], we also have the following results.

Corollary 1. Let \(G\) be a (chemical) tree with \(n\) vertices, \(TI_{f}(G)\) has the minimum value in \(G\), then \(G\cong P_{n}\).

Corollary 2. Let \(G\) be a (chemical) unicyclic graph with \(n\) vertices, \(TI_{f}(G)\) has the minimum value in \(G\), then \(G\cong C_{n}\).

Corollary 3. Let \(G\) be a \((n,m)\) graph, \(TI_{f}(G)\) has the minimum value in \(G\), then \(G\) has \(2m-n \lfloor \frac{2m}{n} \rfloor\) vertices of degree \(\lfloor \frac{2m}{n}\rfloor +1\), \( n-n(\frac{2m}{n}-\lfloor \frac{2m}{n} \rfloor) \) vertices of degree \(\lfloor \frac{2m}{n} \rfloor\).

Corollary 4. Let \(G\) be a \((n,m)\) graph, \(TI_{f}(G)\) has the minimum value in \(G\). If \( n|2m\), then \(G\) is a regular graph and \(TI_{f}(G)=mf(\frac{2m}{n},\frac{2m}{n})\).

3. Concluding Remarks

If \(f(x,y)=\sqrt{x^{2}+y^{2}}\), corresponding chemical index is the Sombor index [11], it has been proof in [12] that the Sombor index meet the conditions of Theorem 1. Our results are the promotion of results of [12]. Our results are suitable for more chemical indices, for example, if \(f(x,y)=x^{2}+y^{2}\), corresponding chemical index is the forgotten index, we can easily proof the forgotten index index meet the conditions of Theorem 1. We use a unified way to consider the extremal values of VDB indices of \((n,m)\)-graphs. We do not need to consider the chemical indices one by one.

Conflicts of Interest:

“The authors declare no conflict of interest.”