On the Lanzhou Indices of Trees under Graph Decoration

Show more

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
$\stackrel{\xaf}{G}$ of *G* has the same vertex set
$V\left(G\right)$, and two vertices are adjacent in
$\stackrel{\xaf}{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}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{d}_{v}^{2}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\text{\hspace{0.17em}}F\left(G\right)={\displaystyle \underset{v\in V\left(G\right)}{\sum}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{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}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{d}_{v}^{2}\stackrel{\xaf}{{d}_{v}}\mathrm{,}$ (2)

where
$\stackrel{\xaf}{{d}_{v}}$ denotes the degree of *v* in
$\stackrel{\xaf}{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{*}}$ corresponding to each edge
$e=uv$ and by joining each new vertex
${v}^{\mathrm{*}}$ 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}+15{n}^{2}-85n+93\right)& \text{if}\text{\hspace{0.17em}}\left(n+1\right)/2\text{\hspace{0.17em}}\text{is}\text{\hspace{0.17em}}\text{even,}\\ \frac{1}{4}\left({n}^{3}+15{n}^{2}-89n+73\right)& \text{if}\text{\hspace{0.17em}}\left(n+1\right)/2\text{\hspace{0.17em}}\text{is}\text{\hspace{0.17em}}\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

$\underset{u\in Y}{\sum}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}{d}_{u}+2l=3n-3,$

and rewriting it as

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

Thus,

$\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}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}c\left({d}_{u}\right)={\displaystyle \underset{u\in Y}{\sum}}\text{\hspace{0.05em}}\text{\hspace{0.05em}}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

$\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}}{\mathrm{max}}\lambda \left({d}_{u}\right),\mathrm{\text{\hspace{0.17em}}}{\lambda}^{-}=\underset{{d}_{u}}{\mathrm{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}+15{n}^{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)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+{\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}+13{n}^{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}+13{n}^{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)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+{\left(\frac{n-5}{2}\right)}^{2}\left(n-1-\frac{n-5}{2}\right)\\ =\frac{1}{4}\left({n}^{3}+11{n}^{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.

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.