Tricyclic Graph with Minimum Randić Index

Abstract

The Randić index of a graph G is the sum of ${\left(d_G\left(u\right)d_G\left(v\right)\right)}^{-\frac{1}{2}}$ over all edges $uv$ of G, where $d_G\left(u\right)$ denotes the degree of vertex u in G. In this paper, we investigate a few graph transformations that decrease the Randić index of a graph. By applying those transformations, we determine the minimum Randić index on tricyclic graphs and characterize the corresponding extremal graphs.

1. Introduction

In this paper, we are concerned with undirected simple connected graphs, unless otherwise specified. Let $G=(V,E)$ be such a graph with n vertices and m edges, which is addressed as an $(n,m)$-graph in what follows. A graph is cyclic if it contains at least one cycle, otherwise it is acyclic. More specifically, an $(n,n+k)$-graph is a tree, unicyclic, bicyclic, tricyclic, or tetracyclic, if $k=-1,0,1,2,3$, respectively. Denote $N_G\left(v\right)$ as the neighbors of vertex v in G, and $d_G\left(v\right)=\left|N_G\left(v\right)\right|$ the degree of v. As usual, let $\Delta \left(G\right)=max\left\{d_G\left(v\right)\right|v\in V\}$ and $\delta \left(G\right)=min\left\{d_G\left(v\right)\right|v\in V\}$. A pendant vertex (or leaf) is a vertex of degree one. The star $S_n$ is a tree with $n-1$ pendant vertices, and the path $P_n$ is a tree with two pendant vertices. For vertex v, we call $N_G^p\left(v\right)=\{u\in N_G\left(v\right)|d_G\left(u\right)=1\}$ pendant neighbors of v, and $N_G^n\left(v\right)=\{u\in N_G\left(v\right)|d_G\left(u\right)>1\}$ non-pendant neighbors. Furthermore, let $d_G^p\left(v\right)=\left|N_G^p\left(v\right)\right|$ and $d_G^n\left(v\right)=\left|N_G^n\left(v\right)\right|$. If $\tilde{E}$ is an edge set, then $G-\tilde{E}$ denotes the graph formed from G by deleting edges in $\tilde{E}$, while $G+\tilde{E}$ means the graph from G by adding edges in $\tilde{E}$. If graphs G and H are isomorphic, we can write it as $G\cong H$.

The Randić index (or R index for short) of G is defined as

$$R\left(G\right)=\sum _{uv\in E}\frac{1}{\sqrt{d_G\left(u\right)d_G\left(v\right)}}.$$

This structural descriptor was proposed as a branching index [1] by Milan Randić in 1975. Since then, the mathematical properties of the R index have been studied extensively. For a comprehensive survey, see [2,3,4,5]. Remarkably, connections between the R index and other graph descriptors have been discovered, such as the graph energy [6], the normalized Laplacian matrix [7], and the information content of the underlying molecular graph [8]. Furthermore, the general Randić index [9,10,11] has attracted much attention in recent years.

From the view of extremal graph theory, Bollobás and Erdös [12] first proved that $S_n$ is the unique graph with the minimum R index for all n-vertex graphs and n-vertex trees. Trees with the second to the fourth minimum R indices have been determined by Zhao and Li in [13]. Caporossi et al. [14] and P. Yu [15] showed that $P_n$ attains the maximum R index in n-vertex trees. In [14], trees and unicyclic graphs with the first and second maximum R indices and bicyclic graphs with the maximum R index are also considered. The unique unicyclic graph with the minimum R index has been determined by Gao and Lu in [16]. Du and Zhou [17] investigated more minimum and maximum R indices of trees, unicyclic, and bicyclic graphs. For instance, the second to the fifth maximum and the second minimum R indices of bicyclic graphs. Furthermore, the tricyclic and tetracyclic graphs with the maximum and the second maximum R indices have been determined in [18,19], while the counterparts with the minimum Randić indices are still unidentified for now.

In this paper, we investigate a few graph transformations that decrease the R index of graphs. With the aid of these transformations, we derive a tricyclic graph with the minimum Randić index as follows.

Theorem 1.

If G is a tricyclic graph of order $n\ge 4$, then $R\left(G\right)\ge \frac{n-4+\sqrt{3}}{\sqrt{n-1}}+1$. And, the equality holds if and only if $G\cong T{R}_n^{★}$, where $T{R}_n^{★}$ is obtained by attaching $n-4$ pendant vertices to one vertex of a complete graph $K_4$ shown as Figure 1.

2. Preliminaries

The following lemmas are required mainly for characterizing transformations in the next section.

Lemma 1.

Suppose $f\left(x\right)$ is twice differentiable, and $f^{″}\left(x\right)>0$. Let $S=f\left(a\right)-f\left(b\right)-f\left(c\right)+f\left(d\right)$ with $a+d=b+c$, $a\le b\le d$ and $a\le c\le d$. Then $S\ge 0$ with equality holding if and only if $a=b$ or $a=c$.

Proof. 

If $a=b$, then $d=c$ from $a+d=b+c$, thereby $S=0$. Similarly $S=0$ if $a=c$. Without loss of generality, we may assume that $a<b\le c<d$. Thus, we obtain $S=f^{\prime }\left({\xi }_1\right)(a-b)+f^{\prime }\left({\xi }_2\right)(d-c)=(b-a)(f^{\prime }\left({\xi }_2\right)-f^{\prime }\left({\xi }_1\right))=(b-a)({\xi }_2-{\xi }_1)f^{″}\left(\eta \right)>0,$ where $a<{\xi }_1<b\le c<{\xi }_2<d$ and ${\xi }_1<\eta <{\xi }_2$. Therefore, the lemma holds clearly. □

Lemma 2.

If $x\ge 2,y\ge 2$, then $f(x,y)=\frac{y-2+\frac{2}{\sqrt{x}}}{\sqrt{y}}-\frac{y-1+\frac{1}{\sqrt{x}}}{\sqrt{y+x-1}}>0.$

Proof. 

Let $g(x,y)=f(x,y)\left(\frac{y-2+\frac{2}{\sqrt{x}}}{\sqrt{y}}+\frac{y-1+\frac{1}{\sqrt{x}}}{\sqrt{y+x-1}}\right)y(x+y-1)=(x-3+\frac{2}{\sqrt{x}})y^2+(4\sqrt{x}-4x+7+\frac{3}{x}-\frac{10}{\sqrt{x}})y+4x-\frac{4}{x}+\frac{8}{\sqrt{x}}-8\sqrt{x}$ with $x\ge 2$ and $y\ge 2$. Note that it suffices to show that $g(x,y)>0$.

Observe that ${(x-3+\frac{2}{\sqrt{x}})}^{\prime }=1-\frac{1}{x^{\frac{3}{2}}}>0$, so $x-3+\frac{2}{\sqrt{x}}\ge 2-3+\frac{2}{\sqrt{2}}>0$. Hence, $\frac{\partial g(x,y)}{\partial y}=2y(x-3+\frac{2}{\sqrt{x}})+(4\sqrt{x}-4x+7+\frac{3}{x}-\frac{10}{\sqrt{x}})\ge 4(x-3+\frac{2}{\sqrt{x}})+(4\sqrt{x}-4x+7+\frac{3}{x}-\frac{10}{\sqrt{x}})=4\sqrt{x}+\frac{3}{x}-\frac{2}{\sqrt{x}}-5\ge 4\sqrt{2}+\frac{3}{2}-\frac{2}{\sqrt{2}}-5>0$ since ${(4\sqrt{x}+\frac{3}{x}-\frac{2}{\sqrt{x}}-5)}^{\prime }=\frac{2}{\sqrt{x}}+\frac{1}{x^{\frac{3}{2}}}-\frac{3}{x^2}>0$. As a consequence, $g(x,y)\ge g(x,2)=2+\frac{2}{x}-\frac{4}{\sqrt{x}}\ge 2+\frac{2}{2}-\frac{4}{\sqrt{2}}>0$ as ${(2+\frac{2}{x}-\frac{4}{\sqrt{x}})}^{\prime }=\frac{2}{x^{\frac{3}{2}}}-\frac{2}{x^2}>0$. Hence, the lemma holds easily. □

Lemma 3.

If $x\ge 3, y\ge 3$ and $k\ge \frac{2}{\sqrt{5}}$, and let

$$f(x,y)=\frac{x-3}{\sqrt{x}}+\frac{y-3}{\sqrt{y}}+\frac{1}{\sqrt{x}\sqrt{y}}-\frac{x+y-5}{\sqrt{x+y-1}}+\left(\frac{k}{\sqrt{x}}-\frac{k}{\sqrt{x+y-1}}\right).$$

Then, $f(x,y)>0$ and $f(y,x)>0$.

Proof. 

Since $f(x,y)\ge \frac{x-3}{\sqrt{x}}+\frac{y-3}{\sqrt{y}}+\frac{1}{\sqrt{x}\sqrt{y}}-\frac{x+y-5}{\sqrt{x+y-1}}+\frac{2}{\sqrt{5}}\left(\frac{1}{\sqrt{x}}-\frac{1}{\sqrt{x+y-1}}\right)=h(x,y)$, then we only have to show $h(x,y)>0$. Consider the gradient

$$\begin{array}{cc}\hfill \frac{\partial h(x,y)}{\partial y}& =\frac{1}{2}\left(\frac{1}{\sqrt{y}}-\frac{1}{\sqrt{x+y-1}}\right)+\frac{3-\frac{1}{\sqrt{x}}}{2y^{\frac{3}{2}}}-\frac{4-\frac{2\sqrt{5}}{5}}{2{\left(x+y-1\right)}^{\frac{3}{2}}}\hfill \\ \hfill & \ge \frac{x-1}{4{\eta }^{\frac{3}{2}}}+\frac{3-\frac{1}{\sqrt{3}}}{2y^{\frac{3}{2}}}-\frac{4-\frac{2\sqrt{5}}{5}}{2{\left(x+y-1\right)}^{\frac{3}{2}}}\hfill \\ \hfill & \ge \frac{(\frac{3-1}{2}+3-\frac{1}{\sqrt{3}})-(4-\frac{2}{\sqrt{5}})}{2{\left(x+y-1\right)}^{\frac{3}{2}}}=\frac{\frac{2}{\sqrt{5}}-\frac{1}{\sqrt{3}}}{2{\left(x+y-1\right)}^{\frac{3}{2}}}>0,\hfill \end{array}$$

where $y<\eta <x+y-1$, hence $h(x,y)\ge h(x,3)$.

Let $g\left(x\right)=x(x+2)\left(\frac{x-3+\frac{1}{\sqrt{3}}+\frac{2}{\sqrt{5}}}{\sqrt{x}}+\frac{x-2+\frac{2}{\sqrt{5}}}{\sqrt{x+2}}\right)h(x,3)=\frac{2\sqrt{3}}{3}{x}^2+\frac{4\sqrt{15}+12\sqrt{5}-100-10\sqrt{3}}{15}x$

$+\frac{304+8\sqrt{15}-72\sqrt{5}-60\sqrt{3}}{15}.$ Since the axis of symmetry of $g\left(x\right)$ is $-\frac{4\sqrt{15}+12\sqrt{5}-100-10\sqrt{3}}{15}/\frac{2\sqrt{3}}{3}/2\approx 2.16493<3$, hence $g\left(x\right)\ge g\left(3\right)=-12\sqrt{5}/5+4/15+4\sqrt{15}/3\approx 0.06408>0$, implying $h(x,3)>0$.

Analogously, it can be shown that $f(y,x)>0$ holds. Therefore, the lemma follows immediately. □

Lemma 4.

If $x\ge 3,y\ge 4$, then

$$\begin{array}{cc}\hfill f(x,y)& =\frac{x-3}{\sqrt{x}}+\frac{1}{\sqrt{x}\sqrt{y}}-\frac{x-2}{\sqrt{x+y-1}}+\frac{1}{\sqrt{2}}\left(\frac{1}{\sqrt{x}}-\frac{1}{\sqrt{x+y-1}}\right)\ge 0.\hfill \end{array}$$

Proof. 

Consider the gradient $\frac{\partial f(x,y)}{\partial y}=\frac{x-2+\frac{\sqrt{2}}{2}}{2{(x+y-1)}^{\frac{3}{2}}}-\frac{1}{2\sqrt{x}{y}^{\frac{3}{2}}}$. Since

$$\begin{array}{cc}\hfill & \frac{\partial f(x,y)}{\partial y}\left(\frac{x-2+\frac{\sqrt{2}}{2}}{2{(x+y-1)}^{\frac{3}{2}}}+\frac{1}{2\sqrt{x}{y}^{\frac{3}{2}}}\right)\left(4{\left(x+y-1\right)}^{3}x\right)\hfill \\ \hfill & =x{\left(x-2+\frac{\sqrt{2}}{2}\right)}^2-\frac{{\left(x+y-1\right)}^3}{y^3}\ge x{\left(x-2+\frac{\sqrt{2}}{2}\right)}^2-\frac{{\left(x+3\right)}^3}{4^3}\hfill \\ \hfill & =\frac{63(x-3)+(60\sqrt{2}-76)}{64}{x}^2+(\frac{252}{64}-2\sqrt{2})x+\frac{9(x-3)}{64}>0,\hfill \end{array}$$

where the last inequality holds by $x\ge 3$, and consequently $\frac{\partial f(x,y)}{\partial y}>0$.

Therefore, it is sufficient to show $f(x,4)\ge 0$. Let $q\left(x\right)=f(x,4)x(x+3)(\frac{x-3+\frac{1}{2}+\frac{\sqrt{2}}{2}}{\sqrt{x}}+\frac{x-2+\frac{\sqrt{2}}{2}}{\sqrt{x+3}})=2x^2+\frac{10\sqrt{2}-51}{4}x+\frac{81-30\sqrt{2}}{4}.$ Since the axis of symmetry of $q\left(x\right)$ is $(-\frac{10\sqrt{2}-51}{4})/4$$\approx 2.3<3$, then $q\left(x\right)\ge q\left(3\right)=0$. Note that $q\left(x\right)$ and $f(x,4)$ have the same sign, so the proof is complete. □

Lemma 5.

Let $x_1,x_2,y$ be integers with $y\ge 3$, and let $f(x_1,x_2,y)=\frac{x_1+\frac{1}{\sqrt{2}}+k}{\sqrt{x_1+x_2}}+\frac{y-2+\frac{1}{\sqrt{2}}}{\sqrt{y}}+\frac{1}{\sqrt{y(x_1+x_2)}}-\frac{x_1+y-2+\sqrt{2}+k}{\sqrt{x_1+x_2+y-2}}-\frac{1}{2},$ then $f(x_1,x_2,y)>0$, if either of the following is satisfied: (1) $x_1\ge 1, 2\le x_2\le 10, k=0$; (2) $x_1=0, 2\le x_2\le 6, k=\frac{1}{\sqrt{3}}$.

Proof. 

(1) Let $h\left(t\right)=\frac{t-\sqrt{2}+2x_2}{2{\left(t+x_2\right)}^{\frac{3}{2}}}$ with $t\ge 1$. Note that $h^{{}^{\prime }}=\frac{-\frac{t}{2}-2x_2+\frac{3\sqrt{2}}{2}}{2{\left(t+x_2\right)}^{\frac{5}{2}}}<0$. Then, we have $\frac{\partial f(x_1,x_2,y)}{\partial x_1}=\frac{x_1-\sqrt{2}+2x_2+(\frac{1}{\sqrt{2}}-\frac{1}{\sqrt{y}})}{2{\left(x_1+x_2\right)}^{\frac{3}{2}}}-\frac{(x_1+y-2)-\sqrt{2}+2x_2}{2{\left((x_1+y-2)+x_2\right)}^{\frac{3}{2}}}>h\left(x_1\right)-h(x_1+y-2)>0,$ hence it suffices to prove $f(1,x_2,y)>0$.

Let $A=\frac{y-2+\frac{1}{\sqrt{2}}}{\sqrt{y}}+\frac{1}{\sqrt{y(1+x_2)}}+\frac{1+\frac{1}{\sqrt{2}}}{\sqrt{1+x_2}}-\frac{1}{2}$, and $B=\frac{y-1+\sqrt{2}}{\sqrt{x_2+y-1}}$. First note that $\frac{1+\frac{1}{\sqrt{2}}}{\sqrt{1+x_2}}-\frac{1}{2}\ge \frac{1+\frac{1}{\sqrt{2}}}{\sqrt{1+10}}-\frac{1}{2}>0$, which means $A>0$. Let $g(x_2,y)=f(1,x_2,y)(A+B)y(x_2+1)(x_2+y-1)=(A^2-B^2)y(x_2+1)(x_2+y-1)=a_1{y}^{\frac{5}{2}}+a_2{y}^2+a_3{y}^{\frac{3}{2}}+a_{4}y+a_5{y}^{\frac{1}{2}}+a_6$. It is easy to see $f(1,x_2,y)>0$ if $g(x_2,y)>0$.

Now, let $b_1=a_1$, and $b_i=\sqrt{3}{b}_{i-1}+a_i$ for $i=2,3,4,5,6$. With assistance of computer, one can get all values of $b_i$ for $2\le x_2\le 10$ as shown in

Table 1. Values of $b_i$ calculated by computer.

${\mathit{x}}_2$	${\mathit{b}}_1$	${\mathit{b}}_2$	${\mathit{b}}_3$	${\mathit{b}}_4$	${\mathit{b}}_5$	${\mathit{b}}_6$
2	2.914	1.975	4.250	4.797	6.224	12.32
3	2.828	3.742	9.896	7.282	8.128	19.11
4	2.634	7.311	18.34	10.15	10.90	29.61
5	2.363	12.74	29.43	13.10	14.33	43.61
6	2.033	20.06	43.05	15.92	18.28	60.95
7	1.657	29.30	59.13	18.44	22.61	81.51
8	1.243	40.47	77.60	20.54	27.23	105.2
9	0.7967	53.58	98.40	22.11	32.07	131.9
10	0.3237	68.64	121.5	23.06	37.06	161.5

, and conclude that $b_i>0$ for each i.

We find that $g(x_2,y)=b_1{y}^{\frac{5}{2}}+a_2{y}^2+a_3{y}^{\frac{3}{2}}+a_{4}y+a_5{y}^{\frac{1}{2}}+a_6\ge \sqrt{3}{b}_1{y}^2+a_2{y}^2+a_3{y}^{\frac{3}{2}}+a_{4}y+a_5{y}^{\frac{1}{2}}+a_6=b_2{y}^2+a_3{y}^{\frac{3}{2}}+a_{4}y+a_5{y}^{\frac{1}{2}}+a_6$. By repeating this process, we arrive at $g(x_2,y)\ge b_6>0$. Therefore, $f(x_1,x_2,y)>0$ holds.

(2) Since the result in this case can be proved by a similar argument as (1), so we omit the details and only give the values of $b_i$ in

Table 2. Values of $b_i$ calculated by computer.

${\mathit{x}}_2$	${\mathit{b}}_1$	${\mathit{b}}_2$	${\mathit{b}}_3$	${\mathit{b}}_4$	${\mathit{b}}_5$	${\mathit{b}}_6$
2	1.633	0.8524	0.5197	1.586	2.748	4.759
3	1.449	1.443	2.912	2.461	3.225	7.122
4	1.138	3.776	7.914	3.697	4.599	13.00
5	0.7443	7.944	15.36	4.898	6.596	22.15
6	0.2925	14.00	25.15	5.812	9.032	34.43

.

The lemma therefore follows easily. □

Lemma 6.

If $y\ge z\ge 2$, then $f(y,z)=(\frac{1}{\sqrt{yz}}-\frac{1}{\sqrt{\left(y+1\right)\left(z-1\right)}})-(\frac{1}{\sqrt{z}}+\frac{1}{\sqrt{y}}-\frac{1}{\sqrt{z-1}}-\frac{1}{\sqrt{y+1}})>0.$

Proof. 

Observe that $f(y,z)=(1-\frac{1}{\sqrt{z}})(1-\frac{1}{\sqrt{y}})-(1-\frac{1}{\sqrt{z-1}})(1-\frac{1}{\sqrt{y+1}}).$ It is obvious that $f(y,2)=\left(1-\frac{1}{\sqrt{2}}\right)\left(1-\frac{1}{\sqrt{y}}\right)>0$.

Now, we consider the case $y\ge z>2$. Let $h(y,z)=ln\left[(1-\frac{1}{\sqrt{z}})(1-\frac{1}{\sqrt{y}})\right]-$$ln\left[(1-\frac{1}{\sqrt{z-1}})(1-\frac{1}{\sqrt{y+1}})\right]$ with $y\ge z>2$. Note that $f(y,z)$ has the same sign with $h(y,z)$ since $ln\left(x\right)$ is increasing for $x>0$. Let $g\left(t\right)=-ln(1-\frac{1}{\sqrt{t}})$ for $t>1$, and $g^{″}\left(t\right)=\frac{3\sqrt{t}-2}{4t^2{\left(\sqrt{t}-1\right)}^2}>0$. Hence, we obtain $h(y,z)=g(z-1)-g\left(z\right)-g\left(y\right)+g(y+1)>0$ by Lemma 1. Therefore, the lemma holds easily. □

Lemma 7.

Let $f(y,z)=\frac{y+k}{\sqrt{y}}+\frac{z+k}{\sqrt{z}}+\frac{k^{\prime }}{\sqrt{yz}}$ with $y\ge z\ge 2$, then $f(y,z)>f(y+1,z-1)$ if it meets one of the following conditions: (1) $k\le 0$ and $k^{\prime }=0$; (2) $k\le -1$, $k^{\prime }=1$.

Proof. 

(1) Let $g\left(t\right)=-\frac{t+k}{\sqrt{t}}$ with $t\ge 1$, and note that $g^{″}\left(t\right)=\frac{t-3k}{4t^{\frac{5}{2}}}>0$. Then we have $f(y,z)-f(y+1,z-1)=g(z-1)-g\left(z\right)-g\left(y\right)+g(y+1)>0$ by Lemma 1.

(2) Let $h\left(t\right)=-\frac{t+k+1}{\sqrt{t}}$ with $t\ge 1$, and note that $h^{″}\left(t\right)=\frac{t-3k-3}{4t^{\frac{5}{2}}}>0$. By Lemma 6, we have $f(y,z)-f(y+1,z-1)\ge \left(\frac{z+k}{\sqrt{z}}+\frac{y+k}{\sqrt{y}}-\frac{z-1+k}{\sqrt{z-1}}-\frac{y+1+k}{\sqrt{y+1}}\right)+\left(\frac{1}{\sqrt{z}}+\frac{1}{\sqrt{y}}-\frac{1}{\sqrt{z-1}}-\frac{1}{\sqrt{y+1}}\right)$$=h(z-1)-h\left(z\right)-h\left(y\right)+h(y+1)>0,$ where the last inequality follows from Lemma 1. □

Lemma 8.

If $x\ge 4,y\ge 4$, then $f(x,y)=\frac{y-3+\frac{\sqrt{3}}{3}+\frac{\sqrt{2}}{2}+\frac{1}{\sqrt{x}}}{\sqrt{y}}+\frac{x-4+\frac{\sqrt{3}}{3}+\sqrt{2}}{\sqrt{x}}-\frac{x+y-7+\frac{2\sqrt{3}}{3}+\sqrt{2}}{\sqrt{x+y-3}}-(\frac{1}{3}+\frac{1}{\sqrt{6}})>0$.

Proof. 

Since

$$\begin{array}{cc}\hfill \frac{\partial f(x,y)}{\partial x}& =\frac{4-\sqrt{2}-\frac{\sqrt{3}}{3}-\frac{1}{\sqrt{y}}}{2x^{\frac{3}{2}}}-\frac{4-\sqrt{2}-\frac{2\sqrt{3}}{3}}{2{(x+y-3)}^{\frac{3}{2}}}+(\frac{1}{2\sqrt{x}}-\frac{1}{2\sqrt{x+y-3}})\hfill \\ \hfill & >\frac{4-\sqrt{2}-\frac{\sqrt{3}}{3}-\frac{1}{\sqrt{4}}}{2x^{\frac{3}{2}}}-\frac{4-\sqrt{2}-\frac{2\sqrt{3}}{3}}{2{(x+y-3)}^{\frac{3}{2}}}>\frac{\frac{\sqrt{3}}{3}-\frac{1}{2}}{2{(x+y-3)}^{\frac{3}{2}}}>0,\hfill \end{array}$$

hence $f(x,y)\ge f(4,y)$. And, moreover,

$$\begin{array}{cc}\hfill \frac{\partial f(4,y)}{\partial y}& =\frac{\frac{5}{2}-\frac{\sqrt{3}}{3}-\frac{\sqrt{2}}{2}}{2y^{\frac{3}{2}}}-\frac{4-\frac{2\sqrt{3}}{3}-\sqrt{2}}{2{\left(y+1\right)}^{\frac{3}{2}}}+(\frac{1}{2\sqrt{y}}-\frac{1}{2\sqrt{y+1}})\hfill \\ \hfill & =\frac{\frac{5}{2}-\frac{\sqrt{3}}{3}-\frac{\sqrt{2}}{2}}{2y^{\frac{3}{2}}}+\frac{1}{4{\eta }^{\frac{3}{2}}}-\frac{4-\frac{2\sqrt{3}}{3}-\sqrt{2}}{2{\left(y+1\right)}^{\frac{3}{2}}}>\frac{\frac{1}{\sqrt{3}}+\frac{1}{\sqrt{2}}-1}{2{\left(y+1\right)}^{\frac{3}{2}}}>0,\hfill \end{array}$$

where $y<\eta <y+1$. Therefore, $f(x,y)\ge f(4,4)\approx 0.05036>0$. □

3. Transformations Decreasing Randić Index

To find tricyclic graphs with a small Randić index, we provide some transformations that decrease the Randić index of graphs. It is worth noting that all transformations defined here preserve the number of vertices and edges of a graph. For simplicity, we will not repeat this property in the sequel.

Definition 1

(Transformation I). Suppose G is a graph with two adjacent vertices u and v such that $N_G\left(v\right)\cap N_G\left(u\right)=\varnothing$. Let graph $G^{\prime }=G-\left\{vw\right|w\in N_G\left(v\right)\setminus u\}+\left\{uw\right|w\in N_G\left(v\right)\setminus u\}$, and we write the transformation as $G^{\prime }=\Gamma (G,u,v)$.

Theorem 2.

Suppose G is a graph with two adjacent vertices u and v such that $N_G\left(v\right)\cap N_G\left(u\right)=\varnothing$. Let $G^{\prime }=\Gamma (G,u,v)$. Then $R\left(G\right)>R\left(G^{\prime }\right)$ if G meets one of the following conditions:

(1) 

v has only one non-pendant neighbor u and $d_G\left(v\right)\ge 2$;

(2) 

v has two non-pendant neighbors u and w with $d_G\left(u\right)\ge d_G\left(w\right)$;

(3) 

v has three non-pendant neighbors $u,v_1,v_2$ and u has three non-pendant neighbors $v,u_1,u_2$ such that $\frac{1}{\sqrt{d_G\left(u_1\right)}}+\frac{1}{\sqrt{d_G\left(u_2\right)}}+\frac{1}{\sqrt{d_G\left(v_2\right)}}+\frac{1}{\sqrt{d_G\left(v_2\right)}}\ge \frac{2}{\sqrt{5}}$;

(4) 

$d_G\left(v\right)\ge 4$ and u has three non-pendant neighbors $v,u_1,u_2$ with $\frac{1}{\sqrt{d_G\left(u_1\right)}}+\frac{1}{\sqrt{d_G\left(u_2\right)}}\ge \frac{1}{\sqrt{2}}$.

Proof. 

Let $\tilde{E}$ be the edge set of G that are not incident with u or v, and $\tilde{R}={\sum }_{pq\in \tilde{E}}$$\frac{1}{\sqrt{d_G\left(p\right)d_G\left(q\right)}}$. And, let $x=d_G\left(u\right)$, $y=d_G\left(v\right)$, $\Delta =R\left(G\right)-R\left(G^{\prime }\right)$. Then,

$$\begin{array}{cc}\hfill R\left(G\right)& =\tilde{R}+\sum _{z\in N_G\left(u\right)\setminus v}\frac{1}{\sqrt{x{d}_G\left(z\right)}}+\sum _{z\in N_G\left(v\right)\setminus u}\frac{1}{\sqrt{y{d}_G\left(z\right)}}+\frac{1}{\sqrt{xy}}\hfill \\ \hfill R\left(G^{\prime }\right)& =\tilde{R}+\left(\sum _{z\in N_G\left(u\right)\setminus v}\frac{1}{\sqrt{d_G\left(z\right)}}+\sum _{z\in N_G\left(v\right)\setminus u}\frac{1}{\sqrt{d_G\left(z\right)}}+1\right)\frac{1}{\sqrt{x+y-1}}.\hfill \end{array}$$

(1) Note that $x,y\ge 2$ and v has $y-1$ pendant neighbors. Then,

$$\begin{array}{cc}\hfill \Delta & =\frac{y-1}{\sqrt{y}}+\frac{1}{\sqrt{xy}}-\frac{y}{\sqrt{x+y-1}}+\sum _{z\in N_G\left(u\right)\setminus v}\frac{1}{\sqrt{d_G\left(z\right)}}(\frac{1}{\sqrt{x}}-\frac{1}{\sqrt{x+y-1}})\hfill \\ \hfill & \ge \frac{y-1}{\sqrt{y}}+\frac{1}{\sqrt{xy}}-\frac{y}{\sqrt{x+y-1}}\hfill \\ \hfill & =\left(\frac{y-2+\frac{2}{\sqrt{x}}}{\sqrt{y}}-\frac{y-1+\frac{1}{\sqrt{x}}}{\sqrt{x+y-1}}\right)+\left(1-\frac{1}{\sqrt{x}}\right)\left(\frac{1}{\sqrt{y}}-\frac{1}{\sqrt{x+y-1}}\right)>0,\hfill \end{array}$$

where the last inequality holds by Lemma 2 and $\frac{1}{\sqrt{y}}>\frac{1}{\sqrt{x+y-1}}$.

(2) Notice that $x\ge 2$, $y\ge 2$, $d_G\left(w\right)\le x$, and v has $y-2$ pendant neighbors in this case. Then,

$$\begin{array}{cc}\hfill \Delta & \ge \frac{y-2}{\sqrt{y}}+\frac{1}{\sqrt{xy}}-\frac{y-1}{\sqrt{y+x-1}}+\frac{1}{\sqrt{d_G\left(w\right)}}\left(\frac{1}{\sqrt{y}}-\frac{1}{\sqrt{y+x-1}}\right)\hfill \\ \hfill & +\sum _{z\in N_G\left(u\right)\setminus v}\frac{1}{\sqrt{d_G\left(z\right)}}(\frac{1}{\sqrt{x}}-\frac{1}{\sqrt{x+y-1}})\hfill \\ \hfill & \ge \frac{y-2}{\sqrt{y}}+\frac{1}{\sqrt{xy}}-\frac{y-1}{\sqrt{y+x-1}}+\frac{1}{\sqrt{x}}\left(\frac{1}{\sqrt{y}}-\frac{1}{\sqrt{y+x-1}}\right)\hfill \\ \hfill & =\frac{y-2+\frac{2}{\sqrt{x}}}{\sqrt{y}}-\frac{y-1+\frac{1}{\sqrt{x}}}{\sqrt{y+x-1}}>0,\hfill \end{array}$$

where the last inequality holds by Lemma 2.

(3) Let $k_1=\frac{1}{\sqrt{d_G\left(u_1\right)}}+\frac{1}{\sqrt{d_G\left(u_2\right)}}$, $k_2=\frac{1}{\sqrt{d_G\left(v_1\right)}}+\frac{1}{\sqrt{d_G\left(v_2\right)}}$, and $p(x,y)=\frac{x-3}{\sqrt{x}}+\frac{y-3}{\sqrt{y}}+\frac{1}{\sqrt{x}\sqrt{y}}-\frac{x+y-5}{\sqrt{x+y-1}}$. Note that $x,y\ge 3$ and $k_1+k_2\ge \frac{2}{\sqrt{5}}$ from the condition. Then,

$$\begin{array}{cc}\hfill \Delta & =p(x,y)+\left(\frac{k_1}{\sqrt{x}}-\frac{k_1}{\sqrt{x+y-1}}\right)+\left(\frac{k_2}{\sqrt{y}}-\frac{k_2}{\sqrt{x+y-1}}\right)\hfill \\ \hfill & =\frac{k_1}{k_1+k_2}\left[p(x,y)+\left(\frac{k_1+k_2}{\sqrt{x}}-\frac{k_1+k_2}{\sqrt{x+y-1}}\right)\right]\hfill \\ \hfill & +\frac{k_2}{k_1+k_2}\left[p(x,y)+\left(\frac{k_1+k_2}{\sqrt{y}}-\frac{k_1+k_2}{\sqrt{x+y-1}}\right)\right]>0,\hfill \end{array}$$

where the last inequality holds by Lemma 3.

(4) Obviously, $x\ge 3$, $y\ge 4$ and $N_G\left(v\right)\setminus u\ne \varnothing$. Then

$$\begin{array}{cc}\hfill \Delta & =\frac{x-3}{\sqrt{x}}+\frac{1}{\sqrt{x}\sqrt{y}}-\frac{x-2}{\sqrt{x+y-1}}\hfill \\ \hfill & +\sum _{z\in N_G\left(v\right)\setminus u}\frac{1}{\sqrt{d_G\left(z\right)}}\left(\frac{1}{\sqrt{y}}-\frac{1}{\sqrt{x+y-1}}\right)\hfill \\ \hfill & +\left(\frac{1}{\sqrt{d_G\left(u_1\right)}}+\frac{1}{\sqrt{d_G\left(u_2\right)}}\right)\left(\frac{1}{\sqrt{x}}-\frac{1}{\sqrt{x+y-1}}\right)\hfill \\ \hfill & >\frac{x-3}{\sqrt{x}}+\frac{1}{\sqrt{x}\sqrt{y}}-\frac{x-2}{\sqrt{x+y-1}}+\frac{1}{\sqrt{2}}\left(\frac{1}{\sqrt{x}}-\frac{1}{\sqrt{x+y-1}}\right)\ge 0,\hfill \end{array}$$

where the last inequality holds by Lemma 4. □

Definition 2

(Transformation II). Suppose G is a graph with two vertices u and v. Let $G^{\prime }$ arise from G by moving k pendant neighbors from u to v, and the transformation can be written as $G^{\prime }=\Theta (G,u,v,k)$. When all pendant neighbors of u are moved to v, this case will be written as $G^{\prime }=\Theta (G,u,v,\infty )$.

Theorem 3.

Suppose G is a graph, and there is a cycle $C=v_0{v}_1{v}_2{v}_0$ in G with $d_G^p\left(v_1\right)\ge 1$ and $d_G^n\left(v_1\right)=2$. Let $G^{\prime }=\Theta (G,v_1,v_0,\infty )$. Then, $R\left(G\right)>R\left(G^{\prime }\right)$ if either of the following is satisfied:

(1) 

$d_G^p\left(v_0\right)\ge 1,2\le d_G^n\left(v_0\right)\le 10$;

(2) 

$2\le d_G^n\left(v_0\right)\le 6$ and there is a vertex $u\in N_G\left(v_0\right)\setminus \{v_1,v_2\}$ with $d_G\left(u\right)\le 3$.

Proof. 

Let $x_1=d_G^p\left(v_0\right)$, $x_2=d_G^n\left(v_0\right)$ and $y=d_G\left(v_1\right)$. Let $f\left(x\right)=\frac{1}{\sqrt{x}}$, then $f^{″}\left(x\right)=\frac{3}{4x^{\frac{5}{2}}}>0$. And, note that $2+(x_1+x_2+y-2)=y+(x_1+x_2)$, $2\le x_1+x_2\le (x_1+x_2+y-2)$ and $2\le y\le (x_1+x_2+y-2)$, then we get $\frac{1}{\sqrt{2}}-\frac{1}{\sqrt{x_1+x_2}}-\frac{1}{\sqrt{y}}+\frac{1}{\sqrt{x_1+x_2+y-2}}\ge 0$ by Lemma 1. Then,

$$\begin{array}{cc}\hfill & R\left(G\right)-R\left(G^{\prime }\right)\hfill \\ \hfill & =\frac{x_1}{\sqrt{x_1+x_2}}+\frac{y-2}{\sqrt{y}}+\frac{1}{\sqrt{y\left(x_1+x_2\right)}}-\frac{x_1+y-2+\frac{1}{\sqrt{2}}}{\sqrt{x_1+x_2+y-2}}\hfill \\ \hfill & +\sum _{z\in N_G^n\left(v_0\right)\setminus \{v_1,v_2\}}\frac{1}{\sqrt{d_G\left(z\right)}}\left(\frac{1}{\sqrt{x_1+x_2}}-\frac{1}{\sqrt{x_1+x_2+y-2}}\right)\hfill \\ \hfill & -\frac{1}{\sqrt{d_G\left(v_2\right)}}\left(\frac{1}{\sqrt{2}}-\frac{1}{\sqrt{x_1+x_2}}-\frac{1}{\sqrt{y}}+\frac{1}{\sqrt{x_1+x_2+y-2}}\right)\hfill \\ \hfill & \ge \frac{x_1}{\sqrt{x_1+x_2}}+\frac{y-2}{\sqrt{y}}+\frac{1}{\sqrt{y\left(x_1+x_2\right)}}-\frac{x_1+y-2+\frac{1}{\sqrt{2}}}{\sqrt{x_1+x_2+y-2}}\hfill \\ \hfill & +\sum _{z\in N_G^n\left(v_0\right)\setminus \{v_1,v_2\}}\frac{1}{\sqrt{d_G\left(z\right)}}\left(\frac{1}{\sqrt{x_1+x_2}}-\frac{1}{\sqrt{x_1+x_2+y-2}}\right)\hfill \\ \hfill & -\frac{1}{\sqrt{2}}\left(\frac{1}{\sqrt{2}}-\frac{1}{\sqrt{x_1+x_2}}-\frac{1}{\sqrt{y}}+\frac{1}{\sqrt{x_1+x_2+y-2}}\right),\hfill \end{array}$$

where the last inequality follows by $d_G\left(v_2\right)\ge 2$.

(1) Note that $x_1\ge 1$, $2\le x_2\le 10$ and $y\ge 3$. Then,

$$\begin{array}{cc}\hfill & R\left(G\right)-R\left(G^{\prime }\right)\hfill \\ \hfill & \ge \frac{x_1}{\sqrt{x_1+x_2}}+\frac{y-2}{\sqrt{y}}+\frac{1}{\sqrt{y\left(x_1+x_2\right)}}-\frac{x_1+y-2+\frac{1}{\sqrt{2}}}{\sqrt{x_1+x_2+y-2}}\hfill \\ \hfill & -\frac{1}{\sqrt{2}}\left(\frac{1}{\sqrt{2}}-\frac{1}{\sqrt{x_1+x_2}}-\frac{1}{\sqrt{y}}+\frac{1}{\sqrt{x_1+x_2+y-2}}\right)\hfill \\ \hfill & =\frac{x_1+\frac{1}{\sqrt{2}}}{\sqrt{x_1+x_2}}+\frac{y-2+\frac{1}{\sqrt{2}}}{\sqrt{y}}+\frac{1}{\sqrt{y\left(x_1+x_2\right)}}-\frac{x_1+y-2+\sqrt{2}}{\sqrt{x_1+x_2+y-2}}-\frac{1}{2}>0,\hfill \end{array}$$

where the last inequality holds by (1) of Lemma 5.

(2) Obviously, the assertion holds if $d_G^p\left(v_0\right)\ge 1$ by (1). Hence, we only need to consider the case $d_G^p\left(v_0\right)=0$. Note that $x_1=0, 2\le x_2\le 6, y\ge 3, d_G\left(u\right)\le 3$, then,

$$\begin{array}{cc}\hfill & R\left(G\right)-R\left(G^{\prime }\right)\hfill \\ \hfill & \ge \left(\frac{y-2}{\sqrt{y}}+\frac{1}{\sqrt{y{x}_2}}\right)-\frac{y-2+\frac{1}{\sqrt{2}}}{\sqrt{x_2+y-2}}+\frac{1}{\sqrt{d_G\left(u\right)}}\left(\frac{1}{\sqrt{x_2}}-\frac{1}{\sqrt{x_2+y-2}}\right)\hfill \\ \hfill & -\frac{1}{\sqrt{2}}\left(\frac{1}{\sqrt{2}}-\frac{1}{\sqrt{x_2}}-\frac{1}{\sqrt{y}}+\frac{1}{\sqrt{x_2+y-2}}\right)\hfill \\ \hfill & \ge \frac{\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}}{\sqrt{x_2}}+\frac{y-2+\frac{1}{\sqrt{2}}}{\sqrt{y}}+\frac{1}{\sqrt{y{x}_2}}-\frac{y-2+\sqrt{2}+\frac{1}{\sqrt{3}}}{\sqrt{x_2+y-2}}-\frac{1}{2}>0,\hfill \end{array}$$

where the last inequality holds by (2) of Lemma 5. □

Theorem 4.

Suppose G is a graph with two vertices u and v such that $d_G\left(u\right)\ge d_G\left(v\right)\ge 2$ and $d_G^p\left(u\right)\ge d_G^p\left(v\right)\ge 1$. Let $G^{\prime }=\Theta (G,v,u,1)$, then $R\left(G\right)>R\left(G^{\prime }\right)$ if $d_G^n\left(v\right)=d_G^n\left(u\right)$ and ${\sum }_{z\in N_G^n\left(u\right)\setminus v}\frac{1}{\sqrt{d_G\left(z\right)}}={\sum }_{z\in N_G^n\left(v\right)\setminus u}\frac{1}{\sqrt{d_G\left(z\right)}}$.

Proof. 

Let $\tilde{E}$ be the edge set of G that are not incident with u or v, and $x=d_G\left(u\right)\ge 2$, $y=d_G\left(v\right)\ge 2$. And, observe that $-|d_G^n\left(u\right)|+{\sum }_{z\in N_G^n\left(u\right)\setminus v}\frac{1}{\sqrt{d_G\left(z\right)}}=-\left|d_G^n\left(v\right)\right|+{\sum }_{z\in N_G^n\left(v\right)\setminus u}$$\frac{1}{\sqrt{d_G\left(z\right)}}$, denoted by k.

If u and v are not adjacent, then $k={\sum }_{z\in N_G^n\left(u\right)}(\frac{1}{\sqrt{d_G\left(z\right)}}-1)\le 0$, so

$$\begin{array}{cc}\hfill R\left(G\right)& =\sum _{pq\in \tilde{E}}\frac{1}{\sqrt{d_G\left(p\right)d_G\left(q\right)}}+\sum _{z\in N_G^n\left(u\right)}\frac{1}{\sqrt{x{d}_G\left(z\right)}}+\frac{x-|N_G^n\left(u\right)|}{\sqrt{x}}\hfill \\ \hfill & +\sum _{z\in N_G^n\left(v\right)}\frac{1}{\sqrt{y{d}_G\left(z\right)}}+\frac{y-|N_G^n\left(v\right)|}{\sqrt{y}}\hfill \\ \hfill & =\sum _{pq\in \tilde{E}}\frac{1}{\sqrt{d_G\left(p\right)d_G\left(q\right)}}+\frac{x+k}{\sqrt{x}}+\frac{y+k}{\sqrt{y}}\hfill \\ \hfill R\left(G^{\prime }\right)& =\sum _{pq\in \tilde{E}}\frac{1}{\sqrt{d_G\left(p\right)d_G\left(q\right)}}+\frac{x+1+k}{\sqrt{x+1}}+\frac{y-1+k}{\sqrt{y-1}}.\hfill \end{array}$$

Therefore, we get $R\left(G\right)>R\left(G^{\prime }\right)$ by (1) of Lemma 7.

If u and v are adjacent, then $k=-1+{\sum }_{z\in N_G^n\left(u\right)\setminus v}(\frac{1}{\sqrt{d_G\left(z\right)}}-1)\le -1$, so

$$\begin{array}{cc}\hfill R\left(G\right)& =\sum _{pq\in \tilde{E}}\frac{1}{\sqrt{d_G\left(p\right)d_G\left(q\right)}}+\sum _{z\in N_G^n\left(u\right)\setminus v}\frac{1}{\sqrt{x{d}_G\left(z\right)}}+\sum _{z\in N_G^n\left(v\right)\setminus u}\frac{1}{\sqrt{y{d}_G\left(z\right)}}\hfill \\ \hfill & +\frac{x-|N_G^n\left(u\right)|}{\sqrt{x}}+\frac{y-|N_G^n\left(v\right)|}{\sqrt{y}}+\frac{1}{\sqrt{xy}}\hfill \\ \hfill & =\sum _{pq\in \tilde{E}}\frac{1}{\sqrt{d_G\left(p\right)d_G\left(q\right)}}+\frac{x+k}{\sqrt{x}}+\frac{y+k}{\sqrt{y}}+\frac{1}{\sqrt{xy}}\hfill \\ \hfill R\left(G^{\prime }\right)& =\sum _{pq\in \tilde{E}}\frac{1}{\sqrt{d_G\left(p\right)d_G\left(q\right)}}+\frac{x+1+k}{\sqrt{x+1}}+\frac{y-1+k}{\sqrt{y-1}}+\frac{1}{\sqrt{(x+1)(y-1)}},\hfill \end{array}$$

hence we have $R\left(G\right)>R\left(G^{\prime }\right)$ by (2) of Lemma 7. Thus, the proof is complete. □

Lemma 9.

Suppose G is a graph with two vertices u and v such that $N_G^n\left(u\right)\setminus v=N_G^n\left(v\right)\setminus u$ and $d_G^p\left(u\right)>0,d_G^p\left(v\right)>0$. Let $G^{\prime }=\Theta (G,v,u,\infty )$, then $R\left(G\right)>R\left(G^{\prime }\right)$.

Proof. 

Observe that if we exchange pendant neighbors of v and u, $R\left(G\right)$ does not change. Hence, the assertion holds easily from Theorem 4. □

4. Main Results

4.1. Undeletable Subgraph and Classification of Tricyclic Graphs

We need the following important definition to start our analysis.

Definition 3

Suppose G is a cyclic graph, then the undeletable subgraph $\varphi \left(G\right)$ of G is defined as a maximum subgraph without a pendant vertex, i.e., the subgraph arising from G by deleting all pendant vertices recursively.

Obviously, $\varphi \left(G\right)$ is connected and $\delta \left(\varphi \right(G\left)\right)\ge 2$. Moreover, an undeletable subgraph of a graph is unique. And, it is easy to verify that the undeletable subgraph of a unicyclic graph is a cycle.

With the definition and Theorem 2, we are able to prove the following crucial lemma:

Lemma 10.

Suppose G is a cyclic $(n,m)$-graph with an undeletable subgraph $\varphi \left(G\right)$. Then, there exists a $(n,m)$-graph $G^{\prime }$ such that $R\left(G\right)>R\left(G^{\prime }\right)$ if there is a vertex $w\in V\left(G\right)\setminus V\left(\varphi \right(G\left)\right)$ with $d_G\left(w\right)>1$.

Proof. 

Let $\widehat{G}=G-E\left(\varphi \left(G\right)\right)$ by deleting all edges of $\varphi \left(G\right)$. By the definition of $\varphi \left(G\right)$, $\widehat{G}$ contains no cycle, i.e., $\widehat{G}$ is a forest.

Let T be the tree of $\widehat{G}$ containing w. We claim that T contains exactly one vertex of $V\left(\varphi \right(G\left)\right)$. First, assume that T contains no vertex of $V\left(\varphi \right(G\left)\right)$, then T is not connected with vertices of $V\left(\varphi \right(G\left)\right)$ in G, thereby G is disconnected, which is a contradiction. Now, assume that T contains at least two vertices of $V\left(\varphi \right(G\left)\right)$, and denote two of which by x and y, then there is a unique path in T that connects them containing a vertex $z\notin V\left(\varphi \right(G\left)\right)$ since $E\left(T\right)\bigcap E\left(\varphi \right(G\left)\right)=\varnothing$. And, there exists a path in $\varphi \left(G\right)$ that connects u and v since $\varphi \left(G\right)$ is connected. Therefore, vertex z lies on a cycle of G, implying that it belongs to $V\left(\varphi \right(G\left)\right)$, which contradicts the fact that $z\notin V\left(\varphi \right(G\left)\right)$. So, T contains exactly one vertex of $V\left(\varphi \right(G\left)\right)$, say $v_0$.

Let $P=v_0{v}_1\dots v_h$ be the longest path from $v_0$ to all other vertices in T. Note that $h\ge 2$ because a path from $v_0$ to a pendant vertex containing w is of length at least two. Hence, $d_G\left(v_{h-1}\right)\ge 2$, $d_G\left(v_{h-2}\right)\ge 2$, and $v_{h-2}$ is the only non-pendant neighbor of $v_{h-1}$. Then, by (1) of Theorem 2, there is an $(n,m)$-graph $G^{\prime }=\Gamma (G,v_{h-2},v_{h-1})$ such that $R\left(G\right)>R\left(G^{\prime }\right)$. □

For a graph G with an undeletable subgraph $\varphi \left(G\right)$, if $d_G\left(w\right)=1$ for each $w\in V\left(G\right)\setminus V\left(\varphi \right(G\left)\right)$, i.e., each $v\in V\left(\varphi \right(G\left)\right)$ only has pendant neighbors in $V\left(G\right)\setminus V\left(\varphi \right(G\left)\right)$, it is said to be a pendant-maximized graph.

Lemma 11.

Suppose G is a pendant-maximized tricyclic $(n,n+2)$-graph with undeletable subgraph $\varphi \left(G\right)$. If there is a vertex $v\in V\left(\varphi \right(G\left)\right)$ with exactly two non-adjacent neighbors in $\varphi \left(G\right)$, then there is an $(n,n+2)$-graph $G^{\prime }$ such that $R\left(G\right)>R\left(G^{\prime }\right)$; otherwise, $\varphi \left(G\right)$ must be one of the 15 graphs as shown in Figure 2, Figure 3 and Figure 4 up to isomorphism.

Proof. 

(1) We first prove the “if” part. Without loss of generality, let the neighbors of v in $\varphi \left(G\right)$ be u and w with $d_G\left(u\right)\ge d_G\left(w\right)$. Observe that $d_G^n\left(v\right)=2$ because G is pendant-maximized and v has two neighbors in $\varphi \left(G\right)$. Hence, $N_G\left(v\right)\cap N_G\left(u\right)=\varnothing$ since u and w are non-adjacent. Therefore, there is an $(n,n+2)$-graph $G^{\prime }=\Gamma (G,u,v)$ such that $R\left(G\right)>R\left(G^{\prime }\right)$ by (2) of Theorem 2.

(2) Now, the “otherwise” part. By the definition of undeletable subgraph, $\varphi \left(G\right)$ is a tricyclic graph, that is, $\left|E\right(\varphi \left(G\right)\left)\right|=\left|V\right(\varphi \left(G\right)\left)\right|+2$ and $\delta \left(\varphi \right(G\left)\right)\ge 2$. In the remaining argument, all degree and neighbors are constrained in $\varphi \left(G\right)$.

We claim that $4\le \left|V\right(\varphi \left(G\right)\left)\right|\le 10$, where the lower bound is obvious by checking graphs of order one to four. We first show there are at most six vertices of degree two in $\varphi \left(G\right)$. Notice that each vertex v of degree two must lie on a cycle of length three because the neighbors of v must be adjacent. Moreover, each cycle of length three contains at most two vertices of degree two, otherwise the cycle is disconnected with other parts of $\varphi \left(G\right)$. Since there are at most three edge-disjoint cycles in a tricyclic graph, thereby at most three edge-disjoint cycles of length three. Hence, by Handshaking Lemma, we have $2\times 6+3\times \left(\right|V\left(\varphi \right(G\left)\right)|-6)\le \left(\right|V\left(\varphi \right(G\left)\right)|+2)\times 2$, implying $\left|V\right(\varphi \left(G\right)\left)\right|\le 10$.

Therefore, we can list all possible graph structures for $\varphi \left(G\right)$ with $4\le \left|V\right(\varphi \left(G\right)\left)\right|\le 10$, which are exactly those shown in Figure 2, Figure 3 and Figure 4. Thus the proof is complete. □

Let ${\mathbb{TR}}_i^j\left(n\right)$ be the set of n-vertex tricyclic graphs obtained from $U_i^j$ by attaching $n-\left|V\right(U_i^j\left)\right|$ pendant vertices to $U_i^j$. It is evident that graphs belonging to ${\mathbb{TR}}_i^j\left(n\right)$ are pendant-maximized. On the other hand, if a pendant-maximized tricyclic graph G with $\varphi \left(G\right)\cong U_i^j$, then $G\in {\mathbb{TR}}_i^j\left(n\right)$.

4.2. Relations between ${\mathbb{TR}}_i^j\left(n\right)$

Suppose $\mathbb{A}$ and $\mathbb{B}$ are two graph sets, and if for any graph $G\in \mathbb{A}$, there is a graph $G^{\prime }\in \mathbb{B}$ such that $R\left(G\right)>R\left(G^{\prime }\right)$, then this relation is written as $R\left(\mathbb{A}\right)>R\left(\mathbb{B}\right)$ or $R\left(\mathbb{B}\right)<R\left(\mathbb{A}\right)$. Our remaining task is to figure out the above described relations between all ${\mathbb{TR}}_i^j\left(n\right)$.

Lemma 12.

$R\left({\mathbb{TR}}_7^4\left(n\right)\right)>R\left({\mathbb{TR}}_7^3\left(n\right)\right)>R\left({\mathbb{TR}}_7^2\left(n\right)\right)>R\left({\mathbb{TR}}_7^1\left(n\right)\right)$.

Proof. 

We prove the results in the order of left to right.

(1) Suppose G is a graph in ${\mathbb{TR}}_7^4\left(n\right)$ with undeletable subgraph labelled as $U_7^4$ in Figure 4. It may be assumed that $d_G^p\left(v_4\right)=0$; otherwise, by Lemma 9, pendant neighbors of $v_4$ can be moved to $v_3$ without increasing $R\left(G\right)$ since $N_G^n\left(v_3\right)\setminus v_4=N_G^n\left(v_4\right)\setminus v_3$. Moreover, we may assume $d_G^p\left(v_6\right)=0$ by similarly reasoning. Then clearly, $d_G\left(v_4\right)=d_G\left(v_6\right)=2$.

Consider first when $d_G^p\left(v_2\right)>0$. If $d_G^p\left(v_3\right)>0$, by (1) of Theorem 3, moving pendant neighbors of $v_3$ to $v_2$ reduces $R\left(G\right)$. So we may assume $d_G^p\left(v_3\right)=0$. Since $d_G^n\left(v_2\right)=d_G^n\left(v_1\right)=3$, and $\frac{1}{\sqrt{v_3}}+\frac{1}{\sqrt{v_4}}+\frac{1}{\sqrt{v_7}}+\frac{1}{\sqrt{v_8}}>\frac{2}{\sqrt{2}}>\frac{2}{\sqrt{5}}$, therefore graph $G^{\prime }=\Gamma (G,v_1,v_2)$ satisfies $R\left(G\right)>R\left(G^{\prime }\right)$ appealing to (3) of Theorem 2.

Now we turn to the case of $d_G^p\left(v_2\right)=0$, that is, $d_G\left(v_2\right)=3$. Note that $d_G^n\left(v_7\right)=d_G^n\left(v_1\right)=3$, and $\frac{1}{\sqrt{v_2}}+\frac{1}{\sqrt{v_8}}+\frac{1}{\sqrt{v_5}}+\frac{1}{\sqrt{v_6}}>\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}>\frac{2}{\sqrt{5}}$, thus graph $G^{″}=\Gamma (G,v_1,v_7)$ satisfies $R\left(G\right)>R\left(G^{″}\right)$ again by (3) of Theorem 2. It is not difficult to check that $G^{\prime }$ and $G^{″}$ both belong to ${\mathbb{TR}}_7^3\left(n\right)$. Thus we have $R\left({\mathbb{TR}}_7^4\left(n\right)\right)>R\left({\mathbb{TR}}_7^3\left(n\right)\right)$.

(2) Let $G\in {\mathbb{TR}}_7^3\left(n\right)$ be a graph with undeletable subgraph as $U_7^3$ in Figure 4. As before, we may assume $d_G^p\left(v_4\right)=0$. Let $G^{\prime }=\Gamma (G,v_2,v_1)$, and obviously $G^{\prime }\in {\mathbb{TR}}_7^2\left(n\right)$. Since $d_G\left(v_1\right)\ge 4$, $d_G^n\left(v_2\right)=3$ and $\frac{1}{\sqrt{v_3}}+\frac{1}{\sqrt{v_4}}\ge \frac{1}{\sqrt{2}}$, then we get $R\left(G\right)>R\left(G^{\prime }\right)$ by (4) of Theorem 2. Thus $R\left({\mathbb{TR}}_7^3\left(n\right)\right)>R\left({\mathbb{TR}}_7^2\left(n\right)\right)$ holds.

(3) Using similar arguments as (2), there is a graph $G^{\prime }=\Gamma (G,v_2,v_1)\in {\mathbb{TR}}_7^1\left(n\right)$ such that $R\left(G\right)>R\left(G^{\prime }\right)$. Hence $R\left({\mathbb{TR}}_7^3\left(n\right)\right)>R\left({\mathbb{TR}}_7^2\left(n\right)\right)$. □

Lemma 13.

$R\left({\mathbb{TR}}_6^3\left(n\right)\right)>R\left({\mathbb{TR}}_6^2\left(n\right)\right)>R\left({\mathbb{TR}}_6^1\left(n\right)\right)$.

Proof. 

We prove the relations from left to right.

(1) Let $G\in {\mathbb{TR}}_6^3\left(n\right)$ be a graph with $\varphi \left(G\right)$ as $U_6^3$ in Figure 4. As before, we assume that $d_G^p\left(v_6\right)=0$.

Let $S=\frac{1}{\sqrt{v_2}}+\frac{1}{\sqrt{v_3}}+\frac{1}{\sqrt{v_5}}+\frac{1}{\sqrt{v_6}}$. If $d_G^p\left(v_2\right)=0$, then $S>\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}>\frac{2}{\sqrt{5}}$. And if $d_G^p\left(v_2\right)>0$, we may assume $d_G^p\left(v_3\right)=0$; otherwise $R\left(G\right)$ can be reduced by moving pendant neighbors of $v_3$ to $v_2$ according to (1) of Theorem 3. Then, we have $S>\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{2}}>\frac{2}{\sqrt{5}}$. Moreover, $d_G^n\left(v_1\right)=d_G^n\left(v_4\right)=3$, hence there is a graph $G^{\prime }=\Gamma (G,v_1,v_4)$ with $R\left(G\right)>R\left(G^{\prime }\right)$ from (3) of Theorem 2. And, it is evident that $G^{\prime }\in {\mathbb{TR}}_6^2\left(n\right)$, thus we obtain $R\left({\mathbb{TR}}_6^3\left(n\right)\right)>R\left({\mathbb{TR}}_6^2\left(n\right)\right)$.

(2) Suppose G is a graph in ${\mathbb{TR}}_6^2\left(n\right)$ with an undeletable subgraph as $U_6^2$ in Figure 4. Using analogous arguments as (1), we can show that $\frac{1}{\sqrt{v_1}}+\frac{1}{\sqrt{v_3}}+\frac{1}{\sqrt{v_4}}+\frac{1}{\sqrt{v_5}}>\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{4}}>\frac{2}{\sqrt{5}}$. Additionally, note that $d_G^n\left(v_2\right)=d_G^n\left(v_6\right)=3$. By (3) of Theorem 2, there is a graph $G^{\prime }=\Gamma (G,v_2,v_6)\in {\mathbb{TR}}_6^1\left(n\right)$ such that $R\left(G\right)>R\left(G^{\prime }\right)$. So, it follows $R\left({\mathbb{TR}}_6^2\left(n\right)\right)>R\left({\mathbb{TR}}_6^1\left(n\right)\right)$ easily. □

Lemma 14.

$R\left({\mathbb{TR}}_4^2\left(n\right)\right)>R\left({\mathbb{TR}}_4^1\left(n\right)\right)$, $R\left({\mathbb{TR}}_7^1\left(n\right)\right)>R\left({\mathbb{TR}}_4^1\left(n\right)\right)$, $R\left({\mathbb{TR}}_6^1\left(n\right)\right)>R\left({\mathbb{TR}}_4^1\left(n\right)\right)$.

Proof. 

We prove the three relations in the order of left to right.

(1) Let $G\in {\mathbb{TR}}_4^2\left(n\right)$ with the undeletable subgraph as $U_4^2$ in Figure 3. As before, we assume $d_G^p\left(v_6\right)=0$, i.e., $d_G\left(v_6\right)=2$. And, notice that $d_G\left(v_4\right)\ge 4,d_G^n\left(v_7\right)=3$. Then, by (4) of Theorem 2, graph $G^{\prime }=\Gamma (G,v_4,v_7)\in {\mathbb{TR}}_4^1\left(n\right)$ satisfies $R\left(G\right)>R\left(G^{\prime }\right)$. Thus, $R\left({\mathbb{TR}}_4^2\left(n\right)\right)>R\left({\mathbb{TR}}_4^1\left(n\right)\right)$ holds clearly.

(2) Let $G\in {\mathbb{TR}}_7^1\left(n\right)$ with an undeletable subgraph as $U_7^1$ in Figure 4. As before, we assume $d_G^p\left(v_3\right)=d_G^p\left(v_5\right)=0$. Note that $d_G^n\left(v_1\right)=6$ and $v_5\in N_G\left(v_1\right)\setminus \{v_2,v_3\}$. If $d_G^p\left(v_2\right)>0$, then by (2) of Theorem 3, $R\left(G\right)$ can be reduced by moving pendant neighbors of $v_2$ to $v_1$. Similarly, it holds for $v_4$. So we may assume $d_G^p\left(v_2\right)=d_G^p\left(v_4\right)=0$.

Let $d_i=d_G\left(v_i\right)$, and we have $d_2=d_3=d_4=d_5=2$ and $d_1\ge 6$. Let $G^{\prime }=G-v_2{v}_3+v_2{v}_5$, then $R\left(G\right)-R\left(G^{\prime }\right)=(\frac{1}{\sqrt{d_1{d}_3}}+\frac{1}{\sqrt{d_1{d}_5}}+\frac{1}{\sqrt{d_2{d}_3}}+\frac{1}{\sqrt{d_4{d}_5}})-(\frac{1}{\sqrt{d_1}}+\frac{1}{\sqrt{d_1(d_5+1)}}+\frac{1}{\sqrt{d_2(d_5+1)}}+\frac{1}{\sqrt{d_4(d_5+1)}})=\frac{1}{\sqrt{d_1}}(\sqrt{2}-1-\frac{1}{\sqrt{3}})+1-\frac{2}{\sqrt{6}}\ge \frac{1}{\sqrt{6}}(\sqrt{2}-1-\frac{1}{\sqrt{3}})+1-\frac{2}{\sqrt{6}}\approx 0.1169>0$. It is easy to check that $G^{\prime }\in {\mathbb{TR}}_4^1$. Thus, $R\left({\mathbb{TR}}_7^1\left(n\right)\right)>R\left({\mathbb{TR}}_4^1\left(n\right)\right)$ follows.

(3) Let $G\in {\mathbb{TR}}_6^1\left(n\right)$ with the undeletable subgraph as $U_6^1$ in Figure 4. As before, we assume $d_G^p\left(v_5\right)=d_G^p\left(v_7\right)=0$. Moreover, we may assume $d_G^p\left(v_3\right)=0$. Otherwise, note that $d_G^n\left(v_1\right)=4$ and $v_5\in N_G\left(v_1\right)\setminus \{v_2,v_3\}$ with $d_G\left(v_5\right)=2$, then appealing to (2) of Theorem 3, moving pendant neighbors of $v_3$ to $v_1$ will decrease $R\left(G\right)$.

Now, notice that $d_G^n\left(v_2\right)=4$, $d_G\left(v_3\right)=2$ and $v_3\in N_G\left(v_2\right)\setminus \{v_6,v_7\}$, we can decrease $R\left(G\right)$ by moving pendant neighbors of $v_6$ to $v_2$ if $d_G^p\left(v_6\right)>0$. Hence, we only have to consider the case $d_G\left(v_6\right)=d_G\left(v_7\right)=2$.

Let $d_i=d_G\left(v_i\right)$, and notice that $d_1\ge 4,d_2\ge 4$. Let $G^{\prime }=G-v_6{v}_7+v_6{v}_1$, then $R\left(G\right)-R\left(G^{\prime }\right)>(\frac{1}{\sqrt{d_2{d}_7}}+\frac{1}{\sqrt{d_6{d}_7}})-(\frac{1}{\sqrt{d_2}}+\frac{1}{\sqrt{d_6(d_1+1)}})=\frac{1}{\sqrt{d_2}}(\frac{1}{\sqrt{2}}-1)+\frac{1}{2}-\frac{1}{\sqrt{2(d_1+1)}}\ge \frac{1}{\sqrt{4}}(\frac{1}{\sqrt{2}}-1)+\frac{1}{2}-\frac{1}{\sqrt{10}}>0.$ It is easy to see that $G^{\prime }\in {\mathbb{TR}}_4^1\left(n\right)$, thus $R\left({\mathbb{TR}}_6^1\left(n\right)\right)>R\left({\mathbb{TR}}_4^1\left(n\right)\right)$ holds. □

Lemma 15.

$R\left({\mathbb{TR}}_5^2\left(n\right)\right)>R\left({\mathbb{TR}}_5^1\left(n\right)\right)>R\left({\mathbb{TR}}_3^1\left(n\right)\right)$, $R\left({\mathbb{TR}}_4^1\left(n\right)\right)>R\left({\mathbb{TR}}_3^1\left(n\right)\right)$, $R\left({\mathbb{TR}}_3^2\left(n\right)\right)$$>R\left({\mathbb{TR}}_3^1\left(n\right)\right)$.

Proof. 

We prove the assertions from left to right.

(1) Let $G\in {\mathbb{TR}}_5^2\left(n\right)$ with the undeletable subgraph as $U_5^2$ in Figure 3. As before, we assume $d_G^p\left(v_6\right)=0$. Observe that $N_G^n\left(v_1\right)\setminus v_2=N_G^n\left(v_2\right)\setminus v_1=\{v_3,v_4\}$. By Lemma 9, we can move pendant neighbors of $v_2$ to $v_1$ and do not increase $R\left(G\right)$ if $d_G^p\left(v_2\right)>0$. Therefore, we may assume that $d_G^p\left(v_2\right)=0$. Notice that $d_G^n\left(v_4\right)=d_G^n\left(v_7\right)=3$ and $\frac{1}{\sqrt{v_1}}+\frac{1}{\sqrt{v_2}}+\frac{1}{\sqrt{v_5}}+\frac{1}{\sqrt{v_6}}>\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}>\frac{2}{\sqrt{5}}$, hence there is $G^{\prime }=\Gamma (G,v_4,v_7)\in {\mathbb{TR}}_5^1\left(n\right)$ such that $R\left(G\right)>R\left(G^{\prime }\right)$ from (3) of Theorem 2. Thus, we obtain $R\left({\mathbb{TR}}_5^2\left(n\right)\right)>R\left({\mathbb{TR}}_5^1\left(n\right)\right)$.

(2) Let $G\in {\mathbb{TR}}_5^1\left(n\right)$ with the undeletable subgraph as $U_5^1$ in Figure 3. By analogous arguments as (1), we may assume that $d_G^p\left(v_6\right)=d_G^p\left(v_2\right)=0$, that is, $d_G\left(v_6\right)=2,d_G\left(v_2\right)=3$. And, note that $d_G^n\left(v_4\right)=4$ and $v_2\in N_G\left(v_4\right)\setminus \{v_5,v_6\}$. Then, according to (2) of Theorem 3, moving pendant neighbors of $v_5$ to $v_4$ reduces $R\left(G\right)$ if $d_G^p\left(v_5\right)>0$. So, we may assume that $d_G^p\left(v_5\right)=0$.

Let $G^{\prime }=G-v_5{v}_6+v_5{v}_1$, and let $d_i=d_G\left(v_i\right)$. Note that $d_1\ge 3,d_4\ge 4,d_G\left(v_5\right)=d_G\left(v_6\right)=2$. Then, $R\left(G\right)-R\left(G^{\prime }\right)>(\frac{1}{\sqrt{d_4{d}_6}}+\frac{1}{\sqrt{d_5{d}_6}})-(\frac{1}{\sqrt{d_4}}+\frac{1}{\sqrt{(d_1+1)d_5}})=\frac{1}{\sqrt{d_4}}(\frac{1}{\sqrt{2}}-1)+\frac{1}{\sqrt{4}}-\frac{1}{\sqrt{2(d_1+1)}}\ge \frac{1}{\sqrt{4}}(\frac{1}{\sqrt{2}}-1)+\frac{1}{\sqrt{4}}-\frac{1}{\sqrt{2(3+1)}}=0$. It is easy to verify that $G^{\prime }\in {\mathbb{TR}}_3^1\left(n\right)$. Therefore, $R\left({\mathbb{TR}}_5^1\left(n\right)\right)>R\left({\mathbb{TR}}_3^1\left(n\right)\right)$ holds.

(3) Let $G\in {\mathbb{TR}}_4^1\left(n\right)$ with the undeletable subgraph as $U_4^1$ in Figure 3. Using similar arguments as (2), we may assume that $d_G^p\left(v_2\right)=d_G^p\left(v_5\right)=d_G^p\left(v_6\right)=0$, i.e., $d_G\left(v_2\right)=d_G\left(v_5\right)=d_G\left(v_6\right)=2$.

Let $G^{\prime }=G-v_3{v}_2+v_3{v}_6$, and let $d_i=d_G\left(v_i\right)$. Note that $d_4\ge 5$. Then, $R\left(G\right)-R\left(G^{\prime }\right)>(\frac{1}{\sqrt{d_2{d}_4}}+\frac{1}{\sqrt{d_4{d}_6}}+\frac{1}{\sqrt{d_2{d}_3}}+\frac{1}{\sqrt{d_5{d}_6}})-(\frac{1}{\sqrt{d_4}}+\frac{1}{\sqrt{d_4(d_6+1)}}+\frac{1}{\sqrt{d_3(d_6+1)}}+\frac{1}{\sqrt{d_5(d_6+1)}})=\frac{1}{\sqrt{d_4}}(\sqrt{2}-1-\frac{1}{\sqrt{3}})+\frac{1}{\sqrt{d_3}}(\frac{1}{\sqrt{2}}-\frac{1}{\sqrt{3}})+\frac{1}{\sqrt{4}}-\frac{1}{\sqrt{6}}\ge \frac{1}{\sqrt{5}}(\sqrt{2}-1-\frac{1}{\sqrt{3}})+\frac{1}{\sqrt{4}}-\frac{1}{\sqrt{6}}\approx 0.01879>0.$ It is clear that $G^{\prime }\in {\mathbb{TR}}_3^1\left(n\right)$. Therefore, we obtain $R\left({\mathbb{TR}}_4^1\left(n\right)\right)>R\left({\mathbb{TR}}_3^1\left(n\right)\right)$ as desired.

(4) Let $G\in {\mathbb{TR}}_3^2\left(n\right)$ with the undeletable subgraph as $U_3^2$ in Figure 2. Let $S=\frac{1}{\sqrt{v_2}}+\frac{1}{\sqrt{v_3}}$. If $d_G^p\left(v_2\right)=0$, i.e., $d_G\left(v_2\right)=3$, then clearly $S\ge \frac{1}{\sqrt{3}}$. Otherwise, note that $d_G^n\left(v_2\right)=3,d_G^p\left(v_2\right)>0$, according to (1) of Theorem 3, moving pendant neighbors of $v_3$ to $v_2$ decreases $R\left(G\right)$ if $d_G^p\left(v_2\right)>0$. So, $S\ge \frac{1}{\sqrt{2}}$ in this case. As a consequence, we have $S\ge \frac{1}{\sqrt{3}}$ by the above argument. Similarly, $\frac{1}{\sqrt{v_5}}+\frac{1}{\sqrt{v_6}}\ge \frac{1}{\sqrt{3}}$, implying that $\frac{1}{\sqrt{v_2}}+\frac{1}{\sqrt{v_3}}+\frac{1}{\sqrt{v_5}}+\frac{1}{\sqrt{v_6}}>\frac{2}{\sqrt{5}}$. And, notice that $d_G^n\left(v_1\right)=d_G^n\left(v_4\right)=3$ and $N_G\left(v_1\right)\bigcap N_G\left(v_4\right)=\varnothing$. Appealing to (3) of Theorem 2, graph $G^{\prime }=\Gamma (G,v_1,v_4)$ satisfies $R\left(G\right)>R\left(G^{\prime }\right)$ with $G^{\prime }\in {\mathbb{TR}}_3^1\left(n\right)$. Therefore, we have $R\left({\mathbb{TR}}_3^2\left(n\right)\right)>R\left({\mathbb{TR}}_3^1\left(n\right)\right)$. □

Before proceeding with more relations, let us define some essential functions and graph classes. Let

$$\begin{array}{cc}\hfill F_1\left(n\right)& =\frac{n-4+\sqrt{3}}{\sqrt{n-1}}+1,F_2\left(n\right)=\frac{n-\frac{9}{2}+\frac{3\sqrt{2}}{2}}{\sqrt{n-1}}+\frac{3\sqrt{2}}{4},\hfill \\ \hfill F_3\left(n\right)& =\frac{n-5+\frac{2\sqrt{3}}{3}+\sqrt{2}}{\sqrt{n-1}}+\frac{1+\sqrt{6}}{3}.\hfill \end{array}$$

For $i=1,2,3$, let $T{R}_i^{*}\left(n\right)$ be n-vertex graphs in ${\mathbb{TR}}_i^1\left(n\right)$ with a vertex of degree $n-1$. It is worth noting that all pendant vertices of $T{R}_i^{*}\left(n\right)$ are adjacent to a single vertex. Further, it can be verified easily that $T{R}_1^{*}\left(n\right)\cong T{R}_n^{★}$.

Lemma 16.

If $G\in {\mathbb{TR}}_1^1\left(n\right)$, then $R\left(G\right)\ge F_1\left(n\right)$ with equality if and only if $G\cong T{R}_1^{*}\left(n\right)$.

Proof. 

If $G\cong T{R}_1^{*}\left(n\right)$, then clearly $R\left(G\right)=F_1\left(n\right)$. If $G\ncong T{R}_1^{*}\left(n\right)$, at least two vertices of $\varphi \left(G\right)$ have pendant neighbors. Suppose the undeletable subgraph $\varphi \left(G\right)$ is labelled as $U_1^1$ in Figure 2. Without loss of generality, we may assume that $d_G^p\left(v_1\right)\ge d_G^p\left(v_2\right)\ge d_G^p\left(v_3\right)\ge d_G^p\left(v_4\right)$. Note that $N_G^n\left(v_1\right)\setminus v_2=N_G^n\left(v_2\right)\setminus v_1=\{v_3,v_4\}$. By Lemma 9, moving pendant neighbors of $v_2$ to $v_1$ will decrease $R\left(G\right)$ if $d_G^p\left(v_2\right)>0$. Similarly, this holds for $v_3$ and $v_4$. So, we can conclude that $R\left(G\right)>F_1\left(n\right)$ if $G\ncong T{R}_1^{*}\left(n\right)$. So, the proof is complete. □

Lemma 17.

If $G\in {\mathbb{TR}}_2^1\left(n\right)$, then $R\left(G\right)\ge F_2\left(n\right)$ with equality if and only if $G\cong T{R}_2^{*}\left(n\right)$.

Proof. 

Suppose the undeletable subgraph $\varphi \left(G\right)$ is labelled as $U_2^1$ in Figure 2. If $G\cong T{R}_2^{*}\left(n\right)$, i.e., one of $v_1,v_2$ is adjacent to all pendant neighbors, then obviously $R\left(G\right)=F_2\left(n\right)$. Then, let us consider the case $G\ncong T{R}_2^{*}\left(n\right)$.

Case 1.

$d_G^p\left(v_1\right)>0,d_G^p\left(v_2\right)>0$, $d_G^p\left(v_3\right)=d_G^p\left(v_4\right)=d_G^p\left(v_5\right)=0$.

It is easy to see that $N_G^n\left(v_1\right)\setminus v_2=N_G^n\left(v_2\right)\setminus v_1=\{v_3,v_4,v_5\}$. By Lemma 9, $R\left(G\right)$ can be reduced by moving pendant neighbors of $v_2$ to $v_1$, implying $R\left(G\right)>F_2\left(n\right)$.

Case 2.

one of $v_3,v_4,v_5$ has pendant neighbors.

We may assume that $d_G^p\left(v_3\right)>0,d_G^p\left(v_4\right)=d_G^p\left(v_5\right)=0$. Notice that $d_G^n\left(v_1\right)=4,d_G\left(v_4\right)=2$, and $v_4\in N_G\left(v_1\right)\setminus \{v_2,v_3\}$. By (2) of Theorem 3, we can move pendant neighbors of $v_3$ to $v_1$ to reduce $R\left(G\right)$. Thus, we have $R\left(G\right)>F_2\left(n\right)$.

Case 3.

at least two of $v_3,v_4,v_5$ have pendant neighbors.

Suppose $d_G^p\left(v_3\right)>0,d_G^p\left(v_4\right)>0$ without loss of generality. Note that $N_G^n\left(v_3\right)\setminus v_4=N_G^n\left(v_4\right)\setminus v_3=\{v_1,v_2\}$. Then, again appealing to Lemma 9, pendant neighbors of $v_4$ can be moved to $v_3$ with $R\left(G\right)$ decreased. Then, we arrive at Case 2, thus $R\left(G\right)>F_2\left(n\right)$.

Therefore, it completes the proof. □

Lemma 18.

If $G\in {\mathbb{TR}}_3^1\left(n\right)$, then $R\left(G\right)\ge F_3\left(n\right)$ with equality if and only if $G\cong T{R}_3^{*}\left(n\right)$.

Proof. 

Suppose the undeletable subgraph $\varphi \left(G\right)$ is labelled as $U_3^1$ in Figure 2. If $G\cong T{R}_3^{*}\left(n\right)$, i.e., $v_1$ is adjacent to all pendant vertices, then obviously $R\left(G\right)=F_3\left(n\right)$. So, we suppose that $G\ncong T{R}_3^{*}\left(n\right)$.

Case 1.

$d_G^p\left(v_2\right)=d_G^p\left(v_3\right)=0$.

Consider first $d_G^p\left(v_5\right)>0$. And, observe that $d_G^n\left(v_1\right)=4,d_G\left(v_2\right)=2$ and $v_2\in N_G\left(v_1\right)\setminus \{v_3,v_5\}$. Then, by (2) of Theorem 3, we can move pendant neighbors of $v_5$ to $v_1$ and get $R\left(G\right)$ smaller. Likewise, this holds for $d_G^p\left(v_4\right)>0$. Therefore, we obtain $R\left(G\right)>F_3\left(n\right)$.

Case 2.

one of $d_G^p\left(v_2\right)>0,d_G^p\left(v_3\right)>0$ holds. Without loss of generality, suppose $d_G^p\left(v_2\right)>0,d_G^p\left(v_3\right)=0$.

Subcase 2.1. $d_G^p\left(v_4\right)=d_G^p\left(v_5\right)=0$. Let $G^{\prime }$ be obtained from G by moving pendant neighbors of $v_2$ to $v_1$. Observe that $d_G\left(v_4\right)=d_G\left(v_5\right)=2,d_G\left(v_3\right)=3$. Let $x=d_G\left(v_1\right)\ge 4$ and let $y=d_G\left(v_2\right)=d_G^p\left(v_2\right)+d_G^p\left(v_2\right)\ge 4$. So, $R\left(G\right)-R\left(G^{\prime }\right)=(\frac{\sqrt{6}}{6}+\frac{y-3+\frac{\sqrt{3}}{3}+\frac{\sqrt{2}}{2}+\frac{1}{\sqrt{x}}}{\sqrt{y}}+\frac{x-4+\frac{\sqrt{3}}{3}+\sqrt{2}}{\sqrt{x}})-(\frac{\sqrt{6}}{3}+\frac{1}{3}+\frac{x+y-7+\frac{2\sqrt{3}}{3}+\sqrt{2}}{\sqrt{x+y-3}})=\frac{y-3+\frac{\sqrt{3}}{3}+\frac{\sqrt{2}}{2}+\frac{1}{\sqrt{x}}}{\sqrt{y}}+\frac{x-4+\frac{\sqrt{3}}{3}+\sqrt{2}}{\sqrt{x}}-\frac{x+y-7+\frac{2\sqrt{3}}{3}+\sqrt{2}}{\sqrt{x+y-3}}-(\frac{1}{3}+\frac{1}{\sqrt{6}})>0$, where the last inequality holds by Lemma 8. Thus, we obtain $R\left(G\right)>F_3\left(n\right)$.

Subcase 2.2. $d_G^p\left(v_4\right)>0,d_G^p\left(v_5\right)=0$. Observe that $d_G^n\left(v_4\right)=2,d_G^n\left(v_2\right)=3$, moving pendant neighbors of $v_4$ to $v_2$ will reduce $R\left(G\right)$ from (1) of Theorem 3. Then, we arrive at Subcase 2.1.

Subcase 2.3. $d_G^p\left(v_4\right)=0,d_G^p\left(v_5\right)>0$. By analogous argument as Case 1, we can move pendant neighbors of $v_5$ to $v_1$, so we get to Subcase 2.1.

Subcase 2.4. $d_G^p\left(v_4\right)>0,d_G^p\left(v_5\right)>0$. Similarly, as Subcase 2.2, pendant neighbors of $v_4$ can be moved to $v_2$ and $R\left(G\right)$ will decrease. Then, we arrive at Subcase 2.3.

According to the four subcases, we obtain $R\left(G\right)>F_3\left(n\right)$ in this case.

Case 3.

$d_G^p\left(v_2\right)>0,d_G^p\left(v_3\right)>0$.

Subcase 3.1. $d_G^p\left(v_4\right)=d_G^p\left(v_5\right)=0$. Note that $d_G^n\left(v_2\right)=d_G^n\left(v_3\right)=3$ and ${\sum }_{u\in N_G^n\left(v_2\right)\setminus v_3}$$\frac{1}{\sqrt{d_G\left(u\right)}}={\sum }_{u\in N_G^n\left(v_3\right)\setminus v_2}\frac{1}{\sqrt{d_G\left(u\right)}}=\frac{1}{\sqrt{d_G\left(v_4\right)}}+\frac{1}{\sqrt{d_G\left(v_1\right)}}$. By Theorem 9, $R\left(G\right)$ can be reduced by moving pendant neighbors of $v_3$ to $v_2$. Then, we get the Subcase 2.1.

Subcase 3.2. $d_G^p\left(v_4\right)+d_G^p\left(v_5\right)>0$. Notice that $d_G^n\left(v_2\right)=3,d_G^n\left(v_4\right)=2$. By (1) of Theorem 3, pendant neighbors of $v_4$ can be moved to $v_2$ with $R\left(G\right)$ decreased if $d_G^p\left(v_4\right)>0$. Analogously, this holds for $v_5$. Thus, we arrive at Subcase 3.1.

Now, we can conclude that $R\left(G\right)>F_3\left(n\right)$ if vertices other than $v_1$ of $\varphi \left(G\right)$ have pendant neighbors. Thus, the proof is complete. □

Lemma 19.

$R\left({\mathbb{TR}}_3^1\left(n\right)\right)>R\left({\mathbb{TR}}_2^1\left(n\right)\right)>R\left({\mathbb{TR}}_1^1\left(n\right)\right)$.

Proof. 

Suppose $\mathbb{A},\mathbb{B}$ are two graph sets with ${min}_{G\in \mathbb{A}}R\left(G\right)<{min}_{G\in \mathbb{B}}R\left(G\right)$. Let $G_A\in \mathbb{A}$ be a graph satisfying $R\left(G_A\right)={min}_{G\in \mathbb{A}}R\left(G\right)$. Then, for any graph $G_B\in \mathbb{B}$, we have $R\left(G_B\right)\ge {min}_{G\in \mathbb{B}}R\left(G\right)>R\left(G_A\right)$, that is, $R\left(\mathbb{A}\right)<R\left(\mathbb{B}\right)$.

So, by Lemmas 16–18, it suffices to show that $F_3\left(n\right)>F_2\left(n\right)>F_1\left(n\right)$. Observe that $n\ge 5$ for $G\in {\mathbb{TR}}_3^1\left(n\right)$ or $G\in {\mathbb{TR}}_2^1\left(n\right)$. Hence, $F_3\left(n\right)-F_2\left(n\right)=\frac{1+\sqrt{6}}{3}-\frac{3\sqrt{2}}{4}+\frac{\frac{2}{\sqrt{3}}-\frac{1}{2}-\frac{1}{\sqrt{2}}}{\sqrt{n-1}}\ge \frac{1+\sqrt{6}}{3}-\frac{3\sqrt{2}}{4}+\frac{\frac{2}{\sqrt{3}}-\frac{1}{2}-\frac{1}{\sqrt{2}}}{\sqrt{4}}\approx 0.06297>0$. And, $F_2\left(n\right)-F_1\left(n\right)=\frac{3\sqrt{2}}{4}-1+\frac{\frac{3}{\sqrt{2}}-\frac{1}{2}-\sqrt{3}}{\sqrt{n-1}}\ge \frac{3\sqrt{2}}{4}-1+\frac{\frac{3}{\sqrt{2}}-\frac{1}{2}-\sqrt{3}}{\sqrt{4}}\approx 0.005295>0$. Therefore, the assertion holds clearly. □

We draw all the relations mentioned here in Figure 5, in which $\mathbb{A}\to \mathbb{B}$ represents $R\left(\mathbb{A}\right)<R\left(\mathbb{B}\right)$.

4.3. The Proof of Theorem 1

Now we are ready to prove our main result.

Proof of Theorem 1.

First, note that $F_1\left(n\right)=\frac{n-4+\sqrt{3}}{\sqrt{n-1}}+1$ and $T{R}_1^{*}\left(n\right)\cong T{R}_n^{★}$, so it is equivalent to show that $R\left(G\right)\ge F_1\left(n\right)$ with equality if and only if $G\cong T{R}_1^{*}\left(n\right)$. Let $\mathcal{F}=\bigcup {\mathbb{TR}}_i^j\left(n\right)$ be the union of all ${\mathbb{TR}}_i^j\left(n\right)$.

If $G\cong T{R}_1^{*}\left(n\right)$, it is clear that $R\left(G\right)=F_1\left(n\right)$.

If $G\in {\mathbb{TR}}_1^1\left(n\right)\setminus \left\{T{R}_1^{*}\left(n\right)\right\}$, we have $R\left(G\right)>F_1\left(n\right)$ by Lemma 16.

If $G\in \mathcal{F}\setminus {\mathbb{TR}}_1^1\left(n\right)$, by Lemmas 12–15, 19 together, we obtain $R\left(G\right)>R\left(T{R}_1^{*}\left(n\right)\right)$$=F_1\left(n\right)$.

If $G\notin \mathcal{F}$ and G is pendant-maximized, by Lemma 11, we can find a graph $G^{\prime }\in \mathcal{F}$ such that $R\left(G\right)>R\left(G^{\prime }\right)\ge F_1\left(n\right)$.

If $G\notin \mathcal{F}$ and G is not pendant-maximized, by Lemmas 10 and 11, we will again find a graph $G^{\prime }\in \mathcal{F}$ such that $R\left(G\right)>R\left(G^{\prime }\right)\ge F_1\left(n\right)$.

Therefore, the theorem holds clearly. □

5. Conclusions

In our current work, we investigate three kinds of graph transformations that decrease the Randić index of graphs, which may be valuable for studying relations between the Randić index and the structure of graphs. For instance, Theorem 4 implies that the pendant neighbors of two vertices of a graph connect to its Randić index predictably. By applying these transformations systematically, the minimum Randić index of tricyclic graphs is determined with the corresponding extremal graphs. In fact, the minimum Randić index of trees, unicyclic, and bicyclic graphs could be obtained by the analogous method without much effort.