On the Lanzhou Indices of Trees under Graph Decoration

Xiaolin Zeng, Tingzeng Wu^*

School of Mathematics and Statistics, Qinghai Nationalities University, Xining, China.

DOI: 10.4236/am.2021.122007                

Abstract

The Lanzhou index of a graph G is defined as the sum of the product between and square of d_u over all vertices u of G, where d_u and are respectively the degree of u in G and the degree of u in the complement graph of G. R(G) is obtained from G by adding a new vertex corresponding to each edge of G, then joining each new vertex to the end vertices of the corresponding edge. Lanzhou index is an important topological index. It is closely related to the forgotten index and first Zagreb index of graphs. In this note, we characterize the bound of Lanzhou index of R(T) of a tree T. And the corresponding extremal graphs are also determined.

Keywords

Lanzhou Index, Zagreb Index, Forgotten Index, Graph Operator

1. Introduction

We use G to denote a simple graph with vertex set $V\left(G\right)=\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ and edge set $E\left(G\right)=\left\{e_1\mathrm{,}{e}_2\mathrm{,}\cdots \mathrm{,}{e}_m\right\}$. The degree of a vertex $v\in V\left(G\right)$ is denoted by $d_v$. The complement graph $\bar{G}$ of G has the same vertex set $V\left(G\right)$, and two vertices are adjacent in $\bar{G}$ if and only if they are not adjacent in G.

Let G be a graph and let $v\in V\left(G\right)$. The first Zagreb index $M_1\left(G\right)$ and forgotten index $F\left(G\right)$ of G are defined respectively as

$M_1\left(G\right)={\displaystyle \underset{v\in V\left(G\right)}{\sum }}{d}_v^2\text{and}F\left(G\right)={\displaystyle \underset{v\in V\left(G\right)}{\sum }}{d}_v^3\mathrm{.}$ (1)

and their theories were well elaborated [1] [2] [3], respectively.

In 2018, Vukičević et al. [4] introduced a new topological index named Lanzhou index, i.e.,

$Lz\left(G\right)={\displaystyle \underset{v\in V\left(G\right)}{\sum }}{d}_v^2\overline{d_v}\mathrm{,}$ (2)

where $\overline{d_v}$ denotes the degree of v in $\bar{G}$. And they pointed out a relation among Lanzhou index, forgotten index and first Zagreb index of G, i.e.,

$Lz\left(G\right)=\left(n-1\right)M_1\left(G\right)-F\left(G\right)\mathrm{.}$ (3)

Furthermore, they determined extremal values of Lanzhou index of trees. For the background of Lanzhou index and related topics, we refer the reader to [4] and the references therein.

Let $R\left(G\right)$ be a graph obtained from G by adding a new vertex $v^{\mathrm{<mo>\; *\; </mo>}}$ corresponding to each edge $e=uv$ and by joining each new vertex $v^{\mathrm{<mo>\; *\; </mo>}}$ to the end vertices u and v of the edge $e=uv$ corresponding to it [5].

Let $T_{\left(n+1\right)/2}$ be a tree with $\left(n+1\right)/2$ vertices. In this work, we focus on properties of Lanzhou index of $R\left(T_{\left(n+1\right)/2}\right)$. We will give the sharp upper bound of Lanzhou index of $R\left(T_{\left(n+1\right)/2}\right)$. And the extremal graph attained the bound is determined.

2. Main Results

For convenience, we use the same definitions and symbols in [4]. The star on n vertices is denoted by $S_n$. A double star $S_{k\mathrm{,}l}$ is a tree obtained from $K_2$ by attaching $k-1$ leaves to one of its vertices and $l-1$ leaves to the other one. Hence, $S_{k\mathrm{,}l}$ has one vertex of degree k, one of degree l, and $k+l-2$ vertices of degree one. A double star on n vertices is balanced if the difference between k and l is the smallest possible. Depending on parity of n, this difference will be either zero for an even n or one for an odd n. Hence, a balanced double star on n vertices is either $S_{n/2,n/2}$ or $S_{\left(n-1\right)/2,\left(n+1\right)/2}$. We denote the balanced double star on n vertices by $BS\left(n\right)$.

By the definition of Lanzhou index of a graph, we direct yields two results as follows.

Lemma 1. Let $R\left(S_{\left(n+1\right)/2}\right)$ be a graph with n vertices. Then $Lz\left(R\left(S_{\left(n+1\right)/2}\right)\right)=4\left(n-3\right)\left(n-1\right)$.

Lemma 2. Let $R\left(B{S}_{\left(n+1\right)/2}\right)$ be a graph with n vertices. Then

$Lz\left(R\left(B{S}_{\left(n+1\right)/2}\right)\right)=(\begin{array}{cc}\frac{1}{4}\left(n^3+15n^2-85n+93\right)& \text{if}\left(n+1\right)/2\text{is}\text{even,}\\ \frac{1}{4}\left(n^3+15n^2-89n+73\right)& \text{if}\left(n+1\right)/2\text{is}\text{odd}\mathrm{.}\end{array}$ (4)

Theorem 1. Let $R\left(T_{\left(n+1\right)/2}\right)$ a graph with $n\left(\ge 27\right)$ vertices. Then

$Lz\left(R\left(S_{\left(n+1\right)/2}\right)\right)\le Lz\left(R\left(T_{\left(n+1\right)/2}\right)\right)\le Lz\left(R\left(B{S}_{\left(n+1\right)/2}\right)\right)\mathrm{.}$ (5)

Proof. Set that $V=V\left(R\left(T_{\left(n+1\right)/2}\right)\right)$ is the vertex set of $R\left(T_{\left(n+1\right)/2}\right)$. Checking the structure of $R\left(T_{\left(n+1\right)/2}\right)$, we know that $\left|V\left(R\left(T_{\left(n+1\right)/2}\right)\right)\right|=n$, and n is odd. Let L denote the set of vertices of degree 2 in $R\left(T_{\left(n+1\right)/2}\right)$. Then V can be decomposed into L and Y, where set $Y=V-L$. Let $l=\left|L\right|$ and $y=\left|Y\right|$ be the set number of L and Y, respectively. By the Euler formula, we have

${\displaystyle \underset{u\in Y}{\sum }}{d}_u+2l=3n-3,$

and rewriting it as

${\displaystyle \underset{u\in Y}{\sum }}\left(d_u-3\right)+3\left(n-l\right)+2l=3n-3.$

Thus,

${\displaystyle \underset{u\in Y}{\sum }}\left(d_u-3\right)=l-3.$ (6)

Now, we define the Lanzhou index of the vertex x as $c\left(x\right)$, and generally case, $c\left(x\right)=x^2\left(n-1-x\right)$. Especially, $c\left(2\right)=4\left(n-3\right)=4n-12$. Therefore, we can get

$Lz\left(R\left(T_{\left(n+1\right)/2}\right)\right)={\displaystyle \underset{u\in V}{\sum }}c\left(d_u\right)={\displaystyle \underset{u\in Y}{\sum }}c\left(d_u\right)+\left(l-3\right)c\left(2\right)+3c\left(2\right).$ (7)

Substituting Equation (6), we can obtain that

$Lz\left(R\left(T_{\left(n+1\right)/2}\right)\right)={\displaystyle \underset{u\in Y}{\sum }}\left[c\left(d_u\right)+\left(d_u-3\right)c\left(2\right)\right]+3c\left(2\right).$ (8)

The following we will prove the right of (8) attained the maximum value. By calculating, we have

${\displaystyle \underset{u\in Y}{\sum }}\left(d_u-3+1\right)={\displaystyle \underset{u\in Y}{\sum }}\left(d_u-2\right)=l-3+r=n-3.$ (9)

Timing $\frac{d_u-2}{d_u-2}$ on the right-hand side of Equation (8), we get

$Lz\left(R\left(T_{\left(n+1\right)/2}\right)\right)={\displaystyle \underset{u\in Y}{\sum }}\frac{c\left(d_u\right)+\left(d_u-3\right)c\left(2\right)}{d_u-2}\left(d_u-2\right)+3c\left(2\right).$ (10)

We define a function $\lambda \left(x\right)$ as follows.

$\lambda \left(x\right)=\frac{c\left(x\right)+\left(x-3\right)c\left(2\right)}{x-2}=\frac{x^2\left(n-1-x\right)+4\left(x-3\right)\left(n-3\right)}{x-2}.$ (11)

${\lambda }^{+}$ and ${\lambda }^{-}$ are its maximum and minimum, respectively.

${\lambda }^{+}=\underset{d_u}{\max }\lambda \left(d_u\right),\mathrm{<mtext>\; \hspace{0.17em}\; </mtext>}{\lambda }^{-}=\underset{d_u}{\min }\lambda \left(d_u\right).$ (12)

Obviously,

${\lambda }^{-}{\displaystyle \underset{u\in Y}{\sum }}\left(d_u-2\right)+3c\left(2\right)\le Lz\left(R\left(T_{\left(n+1\right)/2}\right)\right)\le {\lambda }^{+}{\displaystyle \underset{u\in Y}{\sum }}\left(d_u-2\right)+3c\left(2\right).$ (13)

Substituting Equation (3), we obtain that

${\lambda }^{-}\left(n-3\right)+3c\left(2\right)\le Lz\left(R\left(T_{\left(n+1\right)/2}\right)\right)\le {\lambda }^{+}\left(n-3\right)+3c\left(2\right)\mathrm{.}$ (14)

In fact, $\lambda \left(x\right)$ is a quadratic polynomial with a negative leading coefficient. $x=2$ is the root of its numerator, so we can also write $\lambda \left(x\right)$ as

$\lambda \left(x\right)=-x^2+\left(n-3\right)x+6\left(n-3\right).$ (15)

By checking its values at $x=2$ and $x=n-1$, we have

${\lambda }^{-}=\lambda \left(n-1\right)=-{\left(n-1\right)}^2+\left(n-3\right)\left(n-1\right)+6\left(n-3\right)=4\left(n-4\right).$ (16)

So,

$\begin{array}{c}Lz\left(R\left(T_{\left(n+1\right)/2}\right)\right)\ge {\lambda }^{-}\left(n-3\right)+3c\left(2\right)=4\left(n-4\right)\left(n-3\right)+12\left(n-3\right)\\ =4\left(n-3\right)\left(n-1\right)=Lz\left(R\left(S_{\left(n+1\right)/2}\right)\right).\end{array}$ (17)

Hence, the Lanzhou index is minimized for $R\left(S_{\left(n+1\right)/2}\right)$ and only for $R\left(S_{\left(n+1\right)/2}\right)$.

Now discuss the maximum value of Lanzhou index of $T_{\left(n+1\right)/2}$. First, n must

be odd. When $\lambda \left(x\right)$ reaches its maximum value, $x=\frac{n-3}{2}$, the maximum

value is $\frac{1}{4}\left(n^2+18n-63\right)$. In particular, $\lambda \left(\frac{n-1}{2}\right)=\lambda \left(\frac{n-5}{2}\right)=\frac{1}{4}\left(n^2+18n-67\right)$,

$\lambda \left(\frac{n+1}{2}\right)=\lambda \left(\frac{n-7}{2}\right)=\frac{1}{4}\left(n^2+18n-79\right)$, So, ${\lambda }^{+}=\lambda \left(\frac{n-3}{2}\right)$, it has an upper

bound

$\begin{array}{c}Lz\left(R\left(T_{\left(n+1\right)/2}\right)\right)\le \left(\frac{n^2}{4}+\frac{9n}{2}-\frac{63}{4}\right)\left(n-3\right)+12\left(n-3\right)\\ =\frac{1}{4}\left(n^3+15n^2-69n+45\right).\end{array}$ (18)

Obviously, the value of this upper bound is larger than the value of $Lz\left(R\left(B{S}_{\left(n+1\right)/4,\left(n+1\right)/4}\right)\right)$. And the difference is equal to $4n-12$. In order to demonstrate the conclusion, we must prove that no other $T_n$ has the Lanzhou index closer to this upper bound than the $R\left(B{S}_{\left(n+1\right)/2}\right)$.

Then, we use contradiction method. Suppose that $R\left(B{S}_{\left(n+1\right)/2}\right)$ is not an extremal graph.

There exists an extremal graph $R\left(T_e\right)$ with a maximum of two vertices of high degree (the high degree here means that the degree of these two vertices is

$\frac{n+1}{2}$, $\frac{n-1}{2}$ or $\frac{n-3}{2}$, and the degree of these two vertices can only be even).

Because $R\left(T_e\right)$ is not $R\left(B{S}_{\left(n+1\right)/2}\right)$, then at least the degree of these two vertices

is smaller than $\frac{n+1}{2}$. According to Lemma 2.2 and formula (4), $Lz\left(R\left(T_e\right)\right)$

not exceed $Lz\left(R\left(B{S}_{\left(n+1\right)/2}\right)\right)$. So there are the following cases.

Case 1. When $\frac{n+1}{2}$ is even. And $\frac{n-1}{2}$ is odd.

Suppose that $R\left(T_e\right)$ contains that the degree of one vertex is $\frac{n+1}{2}$, and the another vertex is $\frac{n-1}{2}$, the two vertices must be in Y. In this situation, the

corresponding graph cannot be drawn, because the degree of the two vertices must be even, so a contradiction.

Case 2. When $\frac{n+1}{2}$ is even. And $\frac{n-3}{2}$ is odd.

Suppose that $R\left(T_e\right)$ contains that the degree of one vertex is $\frac{n+1}{2}$, and the another vertex is $\frac{n-3}{2}$, there must be the degree of a vertex is 4 in $R\left(T_e\right)$,

$\begin{array}{c}Lz\left(R\left(T_e\right)\right)=2^2{\left(n-3\right)}^2+{\left(\frac{n+1}{2}\right)}^2\left(n-1-\frac{n+1}{2}\right)\\ +{\left(\frac{n-3}{2}\right)}^2\left(n-1-\frac{n-3}{2}\right)+4^2\left(n-1-4\right)\\ =\frac{1}{4}\left(n^3+13n^2-33n-173\right)<Lz\left(R\left(B{S}_{\left(n+1\right)/2}\right)\right),\end{array}$ (19)

a contradiction.

Case 3. When $\frac{n-1}{2}$ is even. And $\frac{n-3}{2}$ is odd.

Assume that $R\left(T_e\right)$ contains that the degree of one vertex is $\frac{n-1}{2}$, and the another vertex is $\frac{n-3}{2}$, the two vertices must be in Y. In this situation, the

corresponding graph cannot be drawn, because the degree of the two vertices must be even, so a contradiction.

Case 4. When $\frac{n-1}{2}$ is even.

Suppose that $R\left(T_e\right)$ contains that the degree of two vertices are $\frac{n-1}{2}$, there

must be the degree of a vertex is 4 in $R\left(T_e\right)$,

$\begin{array}{c}Lz\left(R\left(T_e\right)\right)=2^2{\left(n-3\right)}^2+2{\left(\frac{n-1}{2}\right)}^2\left(n-1-\frac{n-1}{2}\right)+4^2\left(n-1-4\right)\\ =\frac{1}{4}\left(n^3+13n^2-29n-177\right)<Lz\left(R\left(B{S}_{\left(n+1\right)/2}\right)\right).\end{array}$ (20)

So, a contradiction.

Case 5. When $\frac{n-1}{2}$ is even. And $\frac{n-5}{2}$ is even.

Suppose that $R\left(T_e\right)$ contains that the degree of one vertex is $\frac{n-1}{2}$ and the another vertex is $\frac{n-5}{2}$, there must be the degree of two vertices are 4 in

$R\left(T_e\right)$,

$\begin{array}{c}Lz\left(R\left(T_e\right)\right)=2^2\left(n-3\right)\left(n-4\right)+{\left(\frac{n-1}{2}\right)}^2\left(n-1-\frac{n-1}{2}\right)\\ +{\left(\frac{n-5}{2}\right)}^2\left(n-1-\frac{n-5}{2}\right)\\ =\frac{1}{4}\left(n^3+11n^2+15n-411\right)<Lz\left(R\left(B{S}_{\left(n+1\right)/2}\right)\right).\end{array}$ (21)

So, a contradiction. □

Remark 1. If $n<27$, then the result in Theorem 2.3 is not true.

3. Conclusion

The Lanzhou index is an important chemical index. In this note, we determine sharp upper bound of Lanzhou index of $R\left(T\right)$ when $n\ge 27$. In the future, we will discuss a bound of Lanzhou index of $R\left(G\right)$ of general graph G.

Acknowledgements

This research is supported by the National Natural Science Foundation of China (No. 11761056), the Natural Science Foundation of Qinghai Province (No. 2020-ZJ-920), the Scientific Research Innovation Team in Qinghai Nationalities University.

NOTES

*Corresponding author.

Conflicts of Interest

The authors declare no conflict of interest.

References

[1]	Furtula, B. and Gutman, I. (2015) A Forgotten Topological Index. Journal of Mathematical Chemistry, 53, 1184-1190. https://doi.org/10.1007/s10910-015-0480-z
[2]	Gutman, I. (2013) Degree-Based Topological Indices. Croatica Chemica Acta, 86, 351-361. https://doi.org/10.5562/cca2294
[3]	Randić, M. (1996) Molecular Bonding Profiles. Journal of Mathematical Chemistry, 19, 375-392. https://doi.org/10.1007/BF01166727
[4]	Vukičević, D., Li, Q., Sedlar, J. and Došlić, T. (2018) Lanzhou Index. MATCH Communications in Mathematical and in Computer Chemistry, 80, 863-876.
[5]	Cvetkocić, D.M., Doob, M. and Sachs, H. (1980) Spectra of Graphs Theory and Application. Academic Press, New York.