Menu
Let \(G=(V,\,E)\) be a simple graph with vertex set \(V(G)\) and edge set \(E(G)\). The Lanzhou index of a graph \(G\) is defined by \(Lz(G)=\sum\limits_{u \in V(G)} d_u^2\overline{d}_u\), where \(d_u\) (\(\overline{d}_u \) resp.) denotes the degree of the vertex \(u\) in \(G\) (\(\overline{G}\), the complement graph of \(G\) resp.). It has predictive powers to provide insights of chemical relevant properties of chemical graph structures. In this paper we discuss some properties of Lanzhou index. Several inequalities having lower and upper bound for the Lanzhou index in terms of first, second and third Zagreb indices, radius of graph, eccentric connectivity index, Schultz index, inverse sum indeg index and symmetric division deg index, are discussed. At the end the Lanzhou index of corona and join of graphs have been derived.
Throughout the paper we consider simple, undirected, unweighted graphs only unless it is specified. Let \(G=(V,\,E)\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). The number of vertices and edges are denoted by \(|V(G)|\) and \(|E(G)|\), respectively. The degree of a vertex \(u \in V(G)\), denoted by \(d_G(u)\) (simply \(d_u\) whenever understood) is the number of adjacent vertices to \(u\) in \(G\). The distance between any two vertices \(u\) and \(v\), denoted by \(d(u,v)\) is defined as the length of shortest path between \(u\) and \(v\) in \(G\). The complement graph \(\overline{G}\) of a graph \(G\) is the graph with the same vertex set \(V(G)\) and the vertices are adjacent in \(\overline{G}\) if and only if they are not adjacent in \(G\).
The Zagreb indices were first introduced by Gutman and Trinajstić [1], they are important molecular descriptors and have been closely correlated with many chemical properties[2]. The first Zagreb index \(M_1(G)\) of a graph \(G\) is defined as \[M_1(G)=\sum\limits_{u \in V(G)} d_u^2=\sum\limits_{uv \in E(G)} (d_u+d_v).\] while the second Zagreb index \(M_2(G)\) is defined as \[M_2(G)=\sum\limits_{uv \in E(G)} d_ud_v.\] Furtula and Gutman[3] introduced forgotten topological index (also called F-index) which is defined as \[F(G)=\sum\limits_{u\in V(G)}\,d^3_u=\sum\limits_{uv \in E(G)}\,(d^2_u+d^2_v).\]
In [4], Vukičević et al. considered a linear combination of \(M_1(G)\) and \(F(G)\) of the form \(M_1(G)+\lambda F(G)\), where \(\lambda\) was a free parameter ranging from \(-20\) to \(20\). From the above linear combination, Vukičević et al. introduced in the same paper a new topological index named as Lanzhou index. It is denoted by \(Lz(G)\) and defined by \[Lz(G)=\sum\limits_{u \in V(G)} d_u^2\overline{d}_u,\] where \(\overline{d}_u\) is the degree of the vertex \(u\) in \(\overline{G}\). For its mathematical properties see the paper[4]. For self complimentary graphs, \(d_u=\overline{d}_u\), implying that the Lanzhou index is same as forgotten topological index. In chemical graph theory, many vertex degree based topological indices and their properties have been investigated in[5,6,7,8,9,10,11,12,13,14,15,16,17,18].
In this paper we first discuss some properties of Lanzhou index in Section 2. An upper bound of Lanzhou index for unicyclic graphs has been obtained. The relationships between Lanzhou index and other topological indices such as graph radius, eccentric connectivity index, Schultz index, inverse sum indeg index and symmetric division deg index are derived in Section 3. At the end in Section 4 the Lanzhou index of the join and corona of graphs are provided.
In this section we discuss the properties of the Lanzhou index.
Proposition 1. For a graph \(G\), \(Lz(G)= \sum\limits_{uv \in E(G)} (d_u\overline{d}_u +d_v\overline{d}_v)\).
Proof. We have \[\begin{eqnarray} Lz(G) &=&a\sum\limits_{u\in V(G)}\,d_u^2(n-1-d_u)\\ &=& \sum\limits_{uv \in E(G)}\,\Big( d_u(n-1-d_u) +d_v(n-1-d_v)\Big) \\ &=& \sum\limits_{uv \in E(G)}\,(d_u\overline{d}_u +d_v\overline{d}_v). \end{eqnarray}\]
From the definition of Lanzhou index it is clear that the value of \(Lz(G)\) is a positive integer. The next result shows that the Lanzhou index of a graph is a positive even integer.
Theorem 1. For any graph \(G\), the Lanzhou index \(Lz(G)\) is even.
Proof. Let \(G\) be a graph with \(n\) vertices. By definition of Lanzhou index we have \begin{equation}\tag{1}\label{even odd partition of Lanzhou index} Lz(G)=\sum\limits_{u \in V(G)} d_u^2\overline{d}_u=\sum\limits_{\begin{array}{c} u \in V(G), \\ d_u \mbox{ is even } \end{array} } d_u^2\overline{d}_u + \sum\limits_{\begin{array}{c} u \in V(G), \\ d_u \mbox{ is odd } \end{array}} d_u^2\overline{d}_u. \end{equation}
It is clear to see that the first term of the sum in (\ref{even odd partition of Lanzhou index}) is even. For the second term of the sum in (\ref{even odd partition of Lanzhou index}) we have the following two cases:
\({\bf Case\,1:}\) \(n\) is even. Since \(d_u\) is odd, we have \(\overline{d}_u= n-1-d_u\) is even. And in this case \(d_u^2\overline{d}_u\) is even. Therefore the second term of the sum in (\ref{even odd partition of Lanzhou index}) is even.
\({\bf Case\,2:}\) \(n\) is odd. Since \(d_u\) is odd, we have \(\overline{d}_u= n-1-d_u\) is odd. And in this case \(d_u^2\overline{d}_u\) is odd. It is well known that the number of odd degree vertices in a graph is even. Using the fact that the sum of even number of odd numbers is even, it implies that the second term of the sum in (\ref{even odd partition of Lanzhou index}) is even.
Hence, for any graph, the Lanzhou index \(Lz(G)\) is even.
The union of two graphs \(G\) and \(H\) denoted by \(G\cup H\) is the graph with vertex set \(V(G)\cup V(H)\) and edge set \(E(G)\cup E(H)\). We know that complete graphs and null graphs (graphs with isolated vertices) are the only example of graphs with minimum Lanzhou index \(0\). Likewise, the path of length \(2\) and \(K_2\cup K_1\) are the graphs with second minimum Lanzhou index \(2\).
Proposition 2. For any graph \(G\), \(Lz(G)=2\) if and only if \(G\cong P_3\) or \(G\cong K_2\cup K_1\).
Proof. For \(G\cong P_3\) or \(G\cong K_2\cup K_1\), we have \(Lz(G)=2\). Moreover, \(Lz(K_n)=0=Lz(\overline{K}_n)\). Otherwise, we have \(n\geq 4\) and there exist two vertices \(v\) and \(w\) in \(G\) such that \(1\leq d_v\leq n-2\) and \(1\leq d_w\leq n-2\). Then \[Lz(G)=\sum\limits_{u\in V(G)}\,d_u^2(n-1-d_u)\geq d_v^2(n-1-d_v)+d_w^2(n-1-d_w)>2~\mbox{ as }n\geq 4.\] This completes the proof.
The bound for Lanzhou index of any graph is provided and the graph with extremal value have been characterized in [4].
Proposition 3. [4] Let \(G\) be any graph with \(n\) vertices. Then \[0 \le Lz(G) \le \frac{4}{27}n(n-1)^3.\]
In the following we give some lower and upper bounds for any graph with \(n\) vertices and \(m\) edges having minimum degree \(\delta\) and maximum degree \(\Delta\).
Theorem 2. Let \(G\) be a connected graph with \(n\) vertices and \(m\) edges having minimum degree \(\delta\) and maximum degree \(\Delta\). Then \[(n-1)\delta-\Delta^2 \le \frac{Lz(G)}{2m} \le (n-1)\Delta-\delta^2\] with both equalities hold if and only if \(G\) is a regular graph.
Proof. Since \(\delta\leq d_u\leq \Delta\), by definition of Lanzhou index, we have \[\begin{eqnarray} Lz(G) & =& \sum\limits_{uv \in E(G)} (d_u\overline{d}_u +d_v\overline{d}_v) \\ & =& \sum\limits_{uv \in E(G)} \bigg((n-1)(d_u+d_v) -(d_u^2+d_v^2)\bigg) \\ & \ge & \sum\limits_{uv \in E(G)} \bigg((n-1)2\delta -2\Delta^2\bigg) \\ & =& 2m \bigg((n-1)\delta -\Delta^2\bigg). \end{eqnarray}\] From the above result, we get the lower bound. Moreover, the equality holds in the lower bound if and only if \(d_u=d_v=\delta=\Delta\) for any edge \(uv\in E(G)\), that is, if and only if \(G\) is a regular graph. Again since \(\delta\leq d_u\leq \Delta\), similarly, we can get the upper bound on the Lanzhou index of graph \(G\). Moreover, the right equality holds if and only if \(G\) is a regular graph.
Theorem 3. Let \(G\) be a graph of order \(n\) with \(m\) edges. Then \[Lz(G)+Lz(\overline{G})=(n-1)\sum\limits_{u \in V(G)} d_u \overline{d}_u=(n-1)\,\Big[2(n-1)m-M_1(G)\Big],\] where \(M_1(G)\) is the first Zagreb index of graph \(G\).
Proof. We have \[\begin{eqnarray} Lz(G)+Lz(\overline{G})&=&\sum\limits_{u \in V(G)}\,d_u^2(n-1-d_u)+ \sum\limits_{u \in V(G)}\,\overline{d}_u^2(n-1-\overline{d}_u) \\[2mm] &=&\sum\limits_{u \in V(G)}\,d_u^2(n-1-d_u)+\sum\limits_{u \in V(G)}\,(n-1-d_u)^2d_u \\[2mm] &=& \sum\limits_{u \in V(G)}\,(n-1-d_u)d_u\Big((n-1-d_u)+d_u\Big) \\[2mm] &=& (n-1)\sum\limits_{u \in V(G)}\,\Big[ (n-1)\,d_u-d_u^2\Big]\\[2mm] &=&(n-1)\,\Big[2(n-1)m-M_1(G)\Big]. \end{eqnarray}\]
Corollary 1. For self complementary graph \(G\), \(Lz(G)+Lz(\overline{G})=(n-1)M_1(G)\).
Theorem 4. Let \(G\) be a graph with \(n\) vertices and \(e=uv\) be an edge in \(G\). If \(H=G-e\), then \[Lz(G)-Lz(H)= (2n+1)(d_u+d_v)-3(d_u^2+d_v^2)-2n.\]
Proof. By the definition of Lanzhou index, we have \[\begin{eqnarray} Lz(G)&=&\sum\limits_{x \in V(G)\setminus \lbrace u,\,v \rbrace} d_x^2(n-1-d_x) + d_u^2(n-1-d_u)+d_v^2(n-1-d_v),\\[2mm] Lz(H)&=&\sum\limits_{x \in V(G) \setminus \lbrace u,\, v \rbrace} d_x^2(n-1-d_x) + (d_u-1)^2(n-d_u)+(d_v-1)^2(n-d_v). \end{eqnarray}\]
Therefore we have \[\begin{eqnarray} Lz(G)-Lz(H) &=& -(d_u^2+d_v^2)+(2d_u-1)(n-d_u)+(2d_v-1)(n-d_v) \\ &=& (2n+1)(d_u+d_v)-3(d_u^2+d_v^2)-2n. \end{eqnarray}\] This completes the proof of the theorem.
Let \(T_n\) be a tree with \(n\) vertices and \(T_n^{\Delta}\) denotes the set of all trees on \(n\) vertices with maximum degree at most \(\Delta\). Vukičević et al. [4] obtained the following result:
Proposition 4. [4] Let \(n \ge 8\) be an integer and \(T_n \in T_n^4\). Then \[4n^2 – 18n + 20 \le Lz(T_n) \le 6n^2 + O(n).\]
Theorem 5. Let \(G\) be a unicyclic graph with \(n\,(\ge 8)\) vertices and \(\Delta(G)=4\). Then \[Lz(G)\le 6n^2 + O(n).\]
Proof. Let \(e=uv\) be an edge in \(G\) such that \(H=G-e\), where \(H\) is a tree of order \(n\). Then by Theorem 1, we see that \[Lz(G) \le Lz(H)+ (2n+1)(d_u+d_v),\] where \(d_u\) and \(d_v\) are the degrees of \(u\) and \(v\), respectively.
Since \(d_u,\,d_v\le 4\), from the above result, we have \[Lz(G) \le Lz(H)+ 8(2n+1).\] Since \(H\) is a tree, by Proposition 1, we obtain \[Lz(G) \le 6n^2 + O(n).\] This completes the proof of the theorem.
The eccentricity of a vertex \(v\) in a graph \(G\) is defined as \(ecc_G(v)= max\Big\{d_G(v,u)\,|\,u \in V(G)\Big\}\). The radius of a graph \(G\), denoted by \(r(G)\) is \[r(G)= min\Big\{ecc_G(v)\,|\,v \in V(G)\Big\}.\]
Lemma 1. [19] Let \(G\) be a nontrivial connected graph of order \(n\). For each vertex \(v\) in \(G\), it holds \[ecc_G(v)\leq n-d_v.\] Moreover, the above equality holds together for all vertices in \(G\) if and only if \(G\cong P_4\) or \(G\cong K_n-iK_2\) \((0\leq i\leq \Big\lfloor\frac{n}{2}\Big\rfloor)\), where \(K_n-iK_2\) denotes the graph obtained by removing \(i\) independent edges from \(K_n\).
We now give a relation between \(Lz\) and \(M_1\).
Theorem 6. For any graph \(G\), \begin{equation}\tag{2}\label{1e0} Lz(G) \ge \Big(r(G)-1\Big)M_1(G). \end{equation} Moreover, the equality holds in \((\ref{1e0})\) if and only if \(G\cong K_n\) or \(G\cong K_n-\frac{n}{2}\,K_2\) \((n\) is even\()\).
Proof. For any vertex \(v\) in \(G\) we have \(n- d_v\ge ecc_G(v) \ge r(G)\). Now by the definition of Lanzhou index, we have \[\begin{eqnarray} Lz(G) & =& \sum\limits_{uv \in E(G)} \bigg(d_u(n-1-d_u) +d_v(n-1-d_v)\bigg) \\ & \ge & \sum\limits_{uv \in E(G)}\,\Big(r(G)-1\Big)\,(d_u+d_v) \\ & =& \Big(r(G)-1\Big)\,\sum\limits_{uv \in E(G)} (d_u+d_v) \\ & =& \Big(r(G)-1\Big)\,M_1(G). \end{eqnarray}\]
Suppose that equality holds in \((\ref{1e0})\). Then we have \(n- d_v=ecc_G(v)=r(G)\) for all \(v\in V(G)\). This implies that \(G\) is self-centered graph. By Lemma 1, we have \(G\cong K_n-iK_2\) \((0\leq i\leq \lfloor\frac{n}{2}\rfloor)\). Hence \(G\cong K_n\) or \(G\cong K_n-\frac{n}{2}\,K_2\) (\(n\) is even).
Conversely, one can easily see that the equality holds in \((\ref{1e0})\) for \(K_n\) or for \(K_n-\frac{n}{2}\,K_2\) (\(n\) is even).
Here we give a relation between \(Lz\), \(M_1\) and \(M_2\).
Theorem 7. Let \(G\) be a graph of order \(n\). If \(d_u+d_v\geq n\) for each edge \(uv\in E(G)\), then \[Lz(G)\leq 2M_2(G)-M_1(G).\]
Proof. From the definition of Lanzhou index with the given condition, we have \[\begin{eqnarray} Lz(G)&=&\sum\limits_{uv \in E(G)}\,\bigg(d_u(n-1-d_u)+d_v(n-1-d_v)\bigg)\\[2mm] &\leq&\sum\limits_{uv \in E(G)}\,\bigg(d_u(d_v-1) +d_v(d_u-1)\bigg)\\[2mm] &=&2\,\sum\limits_{uv \in E(G)}\,d_ud_v-\sum\limits_{uv \in E(G)}\,(d_u+d_v)\\[2mm] &=&2\,M_2(G)-M_1(G). \end{eqnarray}\]
We now mention two more relations between \(Lz\), \(M_1\) and \(M_2\).
Theorem 8. Let \(G\) be a graph of order \(n\). Then \[Lz(G)\leq (n-1)\,M_1(G)-2M_2(G)\] with equality holding if and only if each connected component of \(G\) is regular. Moreover, \[(n-1-\Delta)\,M_1(G)\leq Lz(G)\leq (n-1-\delta)\,M_1(G)\] with both equalities hold if and only if \(G\) is a regular graph.
Proof. One can easily see that \(F(G)\geq 2M_2(G)\) with equality holding if and only if each connected component of \(G\) is regular, and \(\delta\,M_1(G)\leq F(G)\leq \Delta\,M_1(G)\) with both equalities hold if and only if \(G\) is a regular graph. Since \(Lz(G)=(n-1)\,M_1(G)-F(G)\), using the above results, we get the required results. This completes the proof of the theorem.
The eccentric connectivity index [18] of a graph \(G\), denoted by \(\xi^c(G)\) is defined as \[\xi^c(G)= \sum\limits_{u \in V(G)}\, d_u\,ecc_G(u).\]
Here we give a relation between \(Lz\), \(M_1\) and \(\xi^c\).
Theorem 9. Let \(G\) be a graph of order \(n\) and minimum degree \(\delta\). Then \[Lz(G)\geq \delta\,\xi^c(G)-M_1(G)\] with equality holding if and only if \(G\cong K_n\) or \(G\cong K_n-\frac{n}{2}\,K_2\) \((n\) is even\()\).
Proof. From the definition of Lanzhou index, we have \[\begin{eqnarray} Lz(G)&=&\sum\limits_{uv \in E(G)}\,\bigg(d_u(n-1-d_u)+d_v(n-1-d_v)\bigg)\\[2mm] &\geq&\sum\limits_{uv \in E(G)}\,\bigg(d_u(ecc_G(u)-1) +d_v(ecc_G(v)-1)\bigg)\\[2mm] &=&\sum\limits_{uv \in E(G)}\,\Big(d_u\,ecc_G(u)+d_v\,ecc_G(v)\Big)-\sum\limits_{uv \in E(G)}\,(d_u+d_v)\\[2mm] &\geq&\delta\sum\limits_{u\in V(G)}\,d_u\,ecc_G(u)-M_1(G)=\delta\,\xi^c(G)-M_1(G). \end{eqnarray}\] By the proof of the Theorem 6, one can easily see that the equality holds if and only if \(G\cong K_n\) or \(G\cong K_n-\frac{n}{2}\,K_2\) \((n\) is even\()\).
We now give a relation between \(Lz\) and \(M_2\).
Theorem 10. Let \(G\) be a connected graph with \(n\) vertices and minimum degree \(\delta\). Then \[\frac{2(n-2)}{\Delta}M_2(G)\leq Lz(G)\leq\frac{2(n-2)}{\delta}M_2(G)\label{1e1}\] with both equalities hold if and only if \(G\) is a regular graph.
Proof. We construct an auxiliary real valued function of two variables \(x\) and \(y\) as \[\begin{eqnarray} g(x,y)&=&\frac{(n-1)(x+y)-(x^2+y^2)}{xy}\nonumber\\[3mm] &=&(n-1)\left(\frac{1}{y}+\frac{1}{x}\right)-\left(\frac{x}{y}+\frac{y}{x}\right),~\mbox{ where }\delta \leq x \leq y \leq \Delta\leq n-1.\nonumber \end{eqnarray}\]
Now, \[\begin{eqnarray} \frac{\partial g(x,y)}{\partial x}&=&(n-1)\left(-\frac{1}{x^2}\right)-\left(\frac{1}{y}-\frac{y}{x^2}\right)\\[3mm] &=&-\frac{1}{x^2}(n-1-y)-\frac{1}{y} < 0,~\mbox{ for }\delta \leq x \leq y \leq \Delta\leq n-1. \end{eqnarray}\]
Therefore, \(g(x,y)\) is monotonically decreasing in the variable \(x\). Since the function \(g(x,y)\) is symmetric in both \(x\) and \(y\), it is also monotonically decreasing in the variable \(y\). Thus we have \(g(x,y)\) attains its maximum value at \((\delta,\,\delta)\) and the minimum value at \((\Delta,\,\Delta)\). Hence \[g(\delta,\,\delta)\leq\frac{2(n-2)}{\delta}~\mbox{ and }~g(\Delta,\,\Delta)\geq \frac{2(n-2)}{\Delta}.\]
This implies that \[(n-1)(d_u+d_v) -(d_u^2+d_v^2)\geq \frac{2(n-2)}{\Delta}\,d_ud_v\] and \[(n-1)(d_u+d_v) -(d_u^2+d_v^2)\leq \frac{2(n-2)}{\delta}\,d_ud_v.\]
Using the above results with the definition of the Lanzhou index, we have \[\begin{eqnarray} Lz(G)&=&\sum\limits_{uv \in E(G)}\,\bigg((n-1)(d_u+d_v)-(d_u^2+d_v^2)\bigg)\\[3mm] &\geq&\sum\limits_{uv \in E(G)}\,\frac{2(n-2)}{\Delta}d_ud_v=\frac{2(n-2)}{\Delta}M_2(G) \end{eqnarray}\] and \[Lz(G)=\sum\limits_{uv \in E(G)}\,\bigg((n-1)(d_u+d_v)-(d_u^2+d_v^2)\bigg)\leq\frac{2(n-2)}{\delta}M_2(G)\]
Moreover, both equalities hold in \((\ref{1e0})\) if and only if \(d_u=d_v=\delta\) or \(d_u=d_v=\Delta\) for any edge \(uv\in E(G)\). Since \(G\) is connected, both equalities hold in \((\ref{1e0})\) if and only if \(G\) is a regular graph.
The irregularity of a graph \(G\), denoted by \(irr(G)\) is defined as \[irr(G)= \sum\limits_{uv \in E(G)} |d_u-d_v|.\] It is also called third Zagreb index of graph. More results on irregularity, one can find in[20,21,22]. Here we give a relation between \(Lz\) with \(M_1(G),\,M_2(G),\,irr(G)\) and \(F(G)\) of graph \(G\).
Theorem 11. Let \(G\) be a connected graph with \(n\) vertices. Then \[(n-1)M_1(G)\leq irr(G)^2+Lz(G)+2M_2(G) \leq (n-1)M_1(G)+2{m\choose 2}\,(\Delta-\delta)^2,\] with left \((right)\) equality holding if and only if \(G\) is a regular graph \((G\) is a regular graph or a bipartite semiregular graph\()\).
Proof. From the definition of irregularity, we have \[\begin{eqnarray}
irr(G)^2 &=& \Big(\sum\limits_{uv \in E(G)}|d_u-d_v|\Big)^2
\\[2mm]
&=&\sum\limits_{uv \in
E(G)}\,(d_u-d_v)^2+2\,\sum\limits_{uv,\,xy \in E(G)\atop uv\neq
xy}|d_u-d_v|\,|d_x-d_y|\\[2mm]
&\le & \sum\limits_{uv \in
E(G)}\,(d_u^2+d_v^2)-2\,\sum\limits_{uv \in E(G)}\,d_u\,d_v+2{m\choose
2}\,(\Delta-\delta)^2\\[2mm]
&=&(n-1)M_1(G)-Lz(G)-2M_2(G)+2{m\choose
2}\,(\Delta-\delta)^2
\end{eqnarray}\] as \(Lz(G)=
(n-1)M_1(G)- F(G)\). Hence we get the right inequality. Moreover,
the equality holds if and only if \(|d_u-d_v|=\Delta-\delta\) for all \(uv\in E(G)\), that is, if and only if \(G\) is a regular graph or a bipartite
semiregular graph as \(G\) is
connected.
Now, \[\begin{eqnarray} irr(G)^2 &=& \Big(\sum\limits_{uv \in E(G)}|d_u-d_v|\Big)^2 \\[2mm] &\ge & \sum\limits_{uv \in E(G)}\,(d_u-d_v)^2 \\[2mm] &=& \sum\limits_{uv \in E(G)}(d_u^2+d_v^2)-2\sum\limits_{uv \in E(G)}d_u.d_v \\[2mm] &=& F(G)-2M_2(G) \\[2mm] &=& (n-1)M_1(G)-Lz(G)-2M_2(G) \end{eqnarray}\] as \(Lz(G)= (n-1)M_1(G)- F(G)\). Hence we get the left inequality. Moreover, the left equality holds if and only if \(d_u=d_v\) for all edges \(uv\in E(G)\), that is, if and only if \(G\) is a regular graph as \(G\) is connected.
The Schultz index of a molecular graph \(G\), introduced by Schultz [23], is defined as \[SI(G)= \frac{1}{2}\sum\limits_{\lbrace u, v\rbrace \subseteq V(G)}(d_u+d_v)d(u,v),\] where \(d(u,v)\) denotes the distance between the vertices \(u\) and \(v\). The Schultz indices have been shown as useful descriptor for molecular design and characterization with desired properties in[2, 24].
The join \(G\vee H\) of two simple graphs \(G\) and \(H\) is the graph with the vertex set \(V(G\vee H)=V(G)\cup V(H)\) and the edge set \(E(G\vee H)=E(G)\cup E(H)\cup \Big\{uv:\,u \in V(G),\,v \in V(H)\Big\}\). The following theorem gives a relation between Schultz index and Lanzhou index.
Theorem 12. Let \(G\) be a connected graph of order \(n\). Then \[SI(G) \ge \frac{1}{2(n-1)}\Big(Lz(G)+F(G)\Big)+\Big(n(n-1)-2m\Big)\,\delta\] with equality holding if and only if \(G\cong K_n\) or \(G\cong K_{\delta}\vee (n-\delta)\,K_1\) \((\delta<n-1)\) or \(G\) is a regular graph with diameter 2.
Proof. By definition of Schultz index we have \[\begin{eqnarray} SI(G) &=& \frac{1}{2} \sum\limits_{\lbrace u, v\rbrace \subseteq V(G)}(d_u+d_v)\,d(u,v) \\[2mm] &=&\frac{1}{2}\sum\limits_{uv\in E(G)}\,(d_u+d_v)+\frac{1}{2}\,\sum\limits_{\lbrace u, v\rbrace \subseteq V(G),\,d(u,\,v)\geq 2}(d_u+d_v)\,d(u,\,v)\\[2mm] &\ge & \frac{1}{2}\,M_1(G)+\sum\limits_{\lbrace u, v\rbrace \subseteq V(G),\,d(u,\,v)\geq 2}(d_u+d_v) \\[2mm] &\ge& \frac{1}{2}\,M_1(G)+2\left({n \choose 2}-m\right)\,\delta \\[2mm] &=& \frac{1}{2(n-1)}\Big(Lz(G)+F(G)\Big)+\Big(n(n-1)-2m\Big)\,\delta. \end{eqnarray}\] The first part of the proof is done.
Suppose that equality holds. Then \(d(u,\,v)=1\) or \(2\) for any pair of vertices \((u,\,v)\). Moreover, \(d_u=d_v=\delta\) when \(d(u,\,v)=2\) for any pair of vertices \((u,\,v)\), that is, all the vertices in \(G\) have degree either \(n-1\) or \(\delta\). If \(\Delta=n-1\), then \(G\cong K_n\) or \(G\cong K_{\delta}\vee (n-\delta)\,K_1\) \((\delta<n-1)\). Otherwise, \(\Delta<n-1\). Then all the vertices in \(G\) are of degree \(\delta\). Hence \(G\) is a regular graph with diameter 2.
Conversely, let \(G\cong K_n\). Then \(Lz(G)=0\), \(F(G)=n(n-1)^3\) and \(SI(G)=n(n-1)^2/2\). Hence the equality holds.
Let \(G\cong K_{\delta}\vee (n-\delta)\,K_1\) \((\delta<n-1)\). Then \(d_1=d_2=\cdots=d_{\delta}=n-1\) and \(d_{\delta+1}=d_{\delta+2}=\cdots=d_n=\delta\). Then \[Lz(G)+F(G)=(n-1)^3\,\delta+(n-1)(n-\delta)\delta^2,\,2m=\delta\,(n-1)+(n-\delta)\,\delta\] and \[SI(G)=\frac{\delta(\delta-1)(n-1)}{2}+(n-\delta)(n-\delta-1)\delta+\frac{\delta(n-\delta)(n-1+\delta)}{2}.\] Now, \[\begin{eqnarray} &&\frac{1}{2(n-1)}\Big(Lz(G)+F(G)\Big)+\Big(n(n-1)-2m\Big)\,\delta\\[2mm] &=&\frac{\delta\,(n-1)^2+(n-\delta)\,\delta^2}{2}+\Big(n(n-1)-\delta\,(n-1)-(n-\delta)\,\delta\Big)\delta\\[2mm] &=&\frac{\delta(\delta-1)(n-1)}{2}+(n-\delta)(n-\delta-1)\delta+\frac{\delta(n-\delta)(n-1+\delta)}{2}\\[2mm] &=&SI(G). \end{eqnarray}\]
Let \(G\) be a regular graph with diameter 2. Then \(d_1=d_2=\cdots=d_n=\delta\). Then \[Lz(G)+F(G)=(n-1)n\,\delta^2,\,2m=n\,\delta~\mbox{ and }~SI(G)=\delta\,\left[m+\left(\frac{n(n-1)}{2}-m\right)2\right].\] Now, \[\begin{eqnarray} &&\frac{1}{2(n-1)}\Big(Lz(G)+F(G)\Big)+\Big(n(n-1)-2m\Big)\,\delta\\[2mm] &=&\frac{n\,\delta^2}{2}+\Big(n(n-1)-n\,\delta\Big)\delta\\[2mm] &=&SI(G). \end{eqnarray}\] This completes the proof of the theorem.
The inverse sum indeg (ISI) index [16] is used as a significant predictor of total surface area for octane isomers. The ISI index is defined as \[ISI(G)=\sum\limits_{ uv \in E(G)} \frac{1}{\frac{1}{d_u}+\frac{1}{d_v}}.\]
Theorem 13. Let \(G\) be a graph with \(n\) vertices and maximum degree \(\Delta\). Then \[Lz(G) \ge 4(n-1-\Delta)ISI(G)\] with equality holding if and only if \(G\) is a regular graph.
Proof. Since \(\Delta\) is the maximum degree in \(G\), we have \[d_u(\Delta-d_u)+d_v(\Delta-d_v)\geq 0,~\mbox{ that is, }~\frac{d_u^2+d_v^2}{d_u+d_v}\leq \Delta\] with equality holding if and only if \(d_u=d_v=\Delta\).
One can easily see that \[(d_u-d_v)^2\geq 0,~\mbox{ that is, }(d_u+d_v)^2\geq 4d_ud_v,~\mbox{ that is, }(d_u+d_v)\geq \frac{4d_ud_v}{d_u+d_v}=\frac{4}{\frac{1}{d_u}+\frac{1}{d_v}}\] with equality holding if and only if \(d_u=d_v\).
Using the above results with the definition of the Lanzhou index, we have \[\begin{eqnarray} Lz(G)&=&\sum\limits_{uv \in E(G)}\,\bigg((n-1)(d_u+d_v)-(d_u^2+d_v^2)\bigg)\\[3mm] &=&\sum\limits_{uv \in E(G)}\,(d_u+d_v)\,\Bigg(n-1-\frac{d_u^2+d_v^2}{d_u+d_v}\Bigg)\\[3mm] &\geq&\sum\limits_{uv \in E(G)}\,(d_u+d_v)\,(n-1-\Delta)\\[3mm] &\geq& 4 (n-1- \Delta)\,\sum\limits_{uv \in E(G)}\,\frac{1}{\frac{1}{d_u}+\frac{1}{d_v}} \\[3mm] & = & 4(n-1-\Delta)ISI(G). \end{eqnarray}\] Moreover, the equality holds if and only if \(d_u=d_v=\Delta\) for any edge \(uv\in E(G)\), that is, if and only if \(G\) is a regular graph.
Corollary 1. Let \(G\) be a graph with \(n\) vertices, \(m\) edges and maximum degree \(\Delta\). Then \[Lz(G) \ge \frac{4m^2\,(n-1-\Delta)}{n}\] with equality holding if and only if \(G\) is a regular graph.
Proof. Since \(ISI(G)\geq \frac{m^2}{n}\), from Theorem 13, we obtain the required result. Moreover, the equality holds if and only if \(G\) is a regular graph.
The symmetric division deg index, \(SDD\), was defined in [17] as \[SDD(G)=\sum\limits_{uv \in E(G)}\,\frac{d_u^2+d_v^2}{d_ud_v}.\] For recent results on \(SDD(G)\) see the papers [25,26,27,28,29] and the references cited therein. Here we give a relation between \(Lz\) and \(SDD\).
Theorem 14. Let \(G\) be a graph with \(n\) vertices and maximum degree \(\Delta\). Then \[Lz(G) \le \Delta^2 \bigg(n(n-1)-SDD(G)\bigg)\] with equality holding if and only if \(G\) is a regular graph.
Proof. Let \(G\cong H\cup p\,K_1\) \((p\geq 0)\), where \(H\) is a graph of order \(n-p\). Since \(n-1-d_u\geq 0\) for all \(u\in V(G)\), by the definition of Lanzhou index, we obtain \[\begin{eqnarray} Lz(G)&=& \sum\limits_{uv \in E(G)}\, \Big[(n-1)(d_u+d_v)-(d_u^2+d_v^2)\Big] \\ &=& \sum\limits_{uv \in E(G)}\, d_u d_v\frac{(n-1)(d_u+d_v)-(d_u^2+d_v^2)}{d_u d_v} \\ &\le & \Delta^2\sum\limits_{uv \in E(G)}\, \bigg(\frac{(n-1)(d_u+d_v)}{d_ud_v}- \frac{d_u^2+d_v^2}{d_ud_v}\bigg) \\ &=& \Delta^2\bigg[(n-1)\sum\limits_{uv \in E(G)} \Big(\frac{1}{d_u}+\frac{1}{d_v}\Big)- \sum\limits_{uv \in E(G)} \frac{d_u^2+d_v^2}{d_ud_v}\bigg] \\ &=& \Delta^2\bigg((n-p)(n-1)-SDD(G)\bigg)\\ &\le & \Delta^2\bigg(n(n-1)-SDD(G)\bigg). \end{eqnarray}\] The first part of the proof is done.
The equality holds if and only if \(d_u=d_v=\Delta\) for any edge \(uv\in E(H)\) and \(p=0\), that is, if and only if \(G\) is a regular graph.
The following theorem provides the formula to find the Lanzhou index of the join of two graphs.
Theorem 15. Let \(G\) and \(H\) be two graphs. Then \[\begin{eqnarray} Lz(G\vee H)= Lz(G)+Lz(H)+4n_2(n_1-1)|E(G)|+4n_1(n_2-1)|E(H)|-2n_2\,M_1(G)&&\\ -2n_1\,M_1(H)+n_1n_2(2n_1n_2-n)-2n_2^2|E(G)|-2n_1^2|E(H)|.~~~~~~~&& \end{eqnarray}\]
Proof. Let \(G\) and \(H\) be two graphs with \(n_1\) and \(n_2\) vertices. Then \(G\vee H\) has \(n_1+n_2\) vertices. We have \(d_{G\vee H}(u)= d_G(u)+n_2\), for \(u \in V(G)\) and \(d_{G\vee H}(u)= d_H(u)+n_1\), for \(u \in V(H)\). By the definition of Lanzhou index, we obtain \[\begin{eqnarray} Lz(G\vee H) &=& \sum\limits_{u \in V(G\vee H)} d_u^2(n_1+n_2-1-d_u) \\ &=& \sum\limits_{u \in V(G)} d_{G\vee H}(u)^2(n_1+n_2-1-d_{G\vee H}(u)) \\ & & \qquad~~~~~~~~~~~~~~~ +\sum\limits_{u \in V(H)} d_{G\vee H}(u)^2 (n_1+n_2-1-d_{G\vee H}(u)). \end{eqnarray}\] Now, \[\begin{eqnarray} & & \sum\limits_{u \in V(G)} d_{G\vee H}(u)^2\Big(n_1+n_2-1-d_{G\vee H}(u)\Big) \\ &=& \sum\limits_{u \in V(G)} \Big(d_{G}(u)+n_2\Big)^2\Big(n_1-1-d_{G}(u)\Big) \\ &=& \sum\limits_{u \in V(G)} d_{G}(u)^2\overline{d}_G(u)+2n_2\sum\limits_{u \in V(G)}d_{G}(u)\Big(n_1-1-d_{G}(u)\Big)+n_2^2\sum\limits_{u \in V(G)}(n_1-1-d_{G}(u)) \\ &=& Lz(G)+4n_2(n_1-1)|E(G)|-2n_2\,M_1(G)+n_2^2\Big(n_1(n_1-1)-2|E(G)|\Big). \end{eqnarray}\] Similarly, we obtain \[\begin{eqnarray} & & \sum\limits_{u \in V(H)} d_{G\vee H}(u)^2\Big(n_1+n_2-1-d_{G\vee H}(u)\Big) \\ &=& Lz(H)+4n_1(n_2-1)|E(H)|-2n_1\,M_1(H)+n_1^2\Big(n_2(n_2-1)-2|E(H)|\Big) \end{eqnarray}\] Combining two above results, we get the required result.
The corona product \(G\circ H\) of two graphs G and H is defined to be the graph \(\Gamma\) obtained by taking one copy of \(G\) (which has \(n_1\) vertices) and \(n_1\) copies of \(H\) (which has \(n_2\) vertices), and then joining the \(i\)-th vertex of \(G\) to every vertex in the \(i\)-th copy of \(H\), \(i=1,\,2,\ldots,\,n_1\). The next theorem provides the Lanzhou index of the corona product of two graphs \(G\) and \(H\).
Theorem 16. Let \(G\) and \(H\) be two graphs of order \(n_1\) and \(n_2\), respectively. Then
\(Lz(G\circ H)=
Lz(G)+n_1Lz(H)+A+n_1B,\)
where
\(A=2n_2(2n_1n_2+2n_1-3n_2-2)|E(G)|-3n_2\,M_1(G)+n_1n^2_2(n_1-1)(n_2+1)\)
and
\(B=2(2n_1n_2+2n_1-5)|E(H)|-3M_1(H)+n_2(n_1n_2+n_1-2).\)
Proof. For any vertex \(u \in
V(G)\), we have \(d_{G\circ H}(u)=
d_G(u)+n_2\) and for any vertex \(u \in
V(H)\), we have \(d_{G\circ H}(u)=
d_H(u)+1\). Now, \[\begin{eqnarray}
&&\sum\limits_{u \in V(G)}\,\Big(d_{G\circ
H}(u)\Big)^2\Big(n_1n_2+n_1-1-d_{G\circ H}(u)\Big)\\[2mm]
&=&\sum\limits_{u \in
V(G)}\,\Big(d_{G}(u)+n_2\Big)^2\Big(n_1n_2+n_1-1-d_{G}(u)-n_2\Big)\\[2mm]
&=&\sum\limits_{u \in
V(G)}\,\Big[d_{G}(u)^2\overline{d}_G(u)-3n_2d_{G}(u)^2+n_2\,(2n_1n_2+2n_1-3n_2-2)\,d_{G}(u)\\
&&~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+n^2_2(n_1-1)(n_2+1)\Big]\\[2mm]
&=&Lz(G)-3n_2\,M_1(G)+2n_2(2n_1n_2+2n_1-3n_2-2)|E(G)|+n_1n^2_2(n_1-1)(n_2+1)
\end{eqnarray}\] and \[\begin{eqnarray}
&&\sum\limits_{u \in V(H)}\,\Big(d_{G\circ
H}(u)\Big)^2\Big(n_1n_2+n_1-1-d_{G\circ H}(u)\Big)\\[2mm]
&=&\sum\limits_{u \in
V(H)}\,\Big(d_{H}(u)+1\Big)^2\Big(n_1n_2+n_1-2-d_{H}(u)\Big)\\[2mm]
&=&\sum\limits_{u \in
V(H)}\,\Big[d_{H}(u)^2\overline{d}_H(u)-3\,d_{H}(u)^2+(2n_1n_2+2n_1-5)d_{H}(u)+n_1n_2+n_1-2\Big]\\[2mm]
&=&Lz(H)-3M_1(H)+2(2n_1n_2+2n_1-5)|E(H)|+n_2(n_1n_2+n_1-2).
\end{eqnarray}\] Using the above results, we obtain \[\begin{eqnarray}
Lz(G\circ H)&=&\sum\limits_{u \in V(G\circ H)}\,\Big(d_{G\circ
H}(u)\Big)^2\Big(n_1n_2+n_1-1-d_{G\circ H}(u)\Big)\\[2mm]
&=&\sum\limits_{u \in
V(G)}\,\Big(d_{G}(u)+n_2\Big)^2\Big(n_1n_2+n_1-1-d_{G}(u)-n_2\Big)\\[2mm]
&&~~~~~~~~~~~~~+\sum\limits_{u \in V(G)}\,\sum\limits_{v \in
V(H)}\,\Big(d_{H}(v)+1\Big)^2\Big(n_1n_2+n_1-2-d_{H}(v)\Big)\\[2mm]
&=&Lz(G)+n_1Lz(H)+A+n_1B,
\end{eqnarray}\] where
\(A=2n_2(2n_1n_2+2n_1-3n_2-2)|E(G)|-3n_2\,M_1(G)+n_1n^2_2(n_1-1)(n_2+1)\)
and
\(B=2(2n_1n_2+2n_1-5)|E(H)|-3M_1(H)+n_2(n_1n_2+n_1-2).\)
This completes the proof of the theorem.
The authors would like to thank the referee for his/her valuable comments which led to an improvement of the original manuscript. The first author gratefully acknowledges support by National Natural Science Foundation of China (61320106005 and 61772214) and the Innovation Scientists and Technicians Troop Construction Projects of Henan Province (154200510012). The second author was supported by the Sungkyun research fund, Sungkyunkwan University, 2017, and National Research Foundation of the Korean government with grant No. 2017R1D1A1B03028642.
The authors declare no conflict of interests.