Spectral radius and extremal graphs for class of unicyclic graph with pendant vertices

Abstract

In this article, we research on the spectral radius of extremal graphs for the unicyclic graphs with girth g mainly by the graft transformation and matching and obtain the upper bounds of the spectral radius of unicyclic graphs.

Introduction

In recent years, more and more results about the bound of spectral radius of graphs are applied to systems with dynamic, catalytic reduction system of ground-vehicle diesel engines and linear parameter varying systems and other system areas.^1–9 Thus, the spectral radius of graphs plays a very important role both in graph theory and system, and a lot of researchers focus on this topic. BF Wu et al. ¹⁰ and MN Elingkam and X Zha ¹¹ proposed the edge graft transformation method to study the spectral radius of graphs. XX Wang and MQ Zhai ¹² gave the k tree with the second maximum spectral radius and the third maximum spectral radius of the original k tree. JS Yuan and JL Shu ¹³ gave an upper bound of the spectral radius of the Halin graphs. An upper bound of the spectral radius in double-star-like tree systems with maximal degree 4 was given in YZ Fan et al. ¹⁴

Since unicyclic graphs contain exactly one cycle, which closely relates with trees, many researchers study the spectral radius of the unicyclic graphs. The specific spectral radius of the unicyclic graphs with given degree sequences was studied in F Belardo et al. ¹⁵ Bounds of spectral radius of unicylic graphs are discussed in previous studies.^16–18 The upper bound of the Laplacian spectral radius was presented in Zhou and Xu ¹⁹ using the Cauchy–Schwarz inequality, Li and Feng ²⁰ gave the maximum eigenvalue of graphs, and Hou and Li ²¹ mainly studied the bounds of the spectral radius of the tree graphs with some certain matching. Mao et al. ²² researched on the spectral radius of unicyclic and bicyclic graphs containing n vertices with k pendant vertices.

Although a lot of researchers give the bounds of the spectral radius of unicyclic graph, few use the method of extremal graphs, which are obtained by graft transformation, of the original unicyclic graph. Here, we obtained the upper bound of the spectral radius of the unicyclic graphs.

Preliminaries

Readers can refer to Liu ²³ for notation and terminology not defined in the article. Only simple graphs are considered in this article. Denote the adjacency matrix of a graph G by $A(G)$ . The characteristic polynomial of a graph G is the characteristic polynomial of $A(G)$ , denoted by $\Psi (G)$ . Let ${\lambda }_1\cdots {\lambda }_n$ denote the eigenvalues of $A(G)$ with ${\lambda }_1\ge {\lambda }_2\ge \cdots \ge {\lambda }_n$ , where ${\lambda }_1\cdots {\lambda }_n$ is called the spectrum of G, and ${\lambda }_1(G)$ is called the spectral radius of G denoted by $\rho (G)$ . By Perron–Frobenius Theorem, ² the spectral radius is unique and all the components in its corresponding eigenvector $x=(x_1,x_2,\dots ,x_n{)}^T$ are positive. Denote the degree of v by $d(v)$ , and the cycles containing u by $C_G(u)$ .

For a graph G, denote a matching of G by M. If a vertex is incident with an edge of a matching M, then the vertex is called saturated by M. The degree sum of all neighbors of v is called the second degree of v, denoted by T(v).

In this article, we will study the upper bounds of the spectral radius and the extremal graphs of unicyclic graphs. In section “Lemmas,” we introduce some lemmas needed in the proof of the main results in the article. We give the proof of our main results in section “Main results.”

Lemmas

In this section, we will introduce some lemmas used in the next section.

Lemma 1

For any vertex u of a graph G⁶

$$\begin{array}{l}\Psi (G;\lambda )=\lambda \Psi (G-v;\lambda )-{\displaystyle \sum _{u-v}\Psi }(G-v-u;\lambda )-2\\ {\displaystyle \sum _{z\in Z(v)}\Psi }(G-V(z);\lambda )\end{array}$$

(1)

Lemma 2

Let $S_j(A)$ be the jth row sum, then for $\forall f(x)\in \Re [x]$ (ℜ is the polynomial ring on real number field), we have ⁷

$$\underset{j}{min}{S}_j(f(A))\le f(\rho )\le \underset{j}{max}{S}_j(f(A))$$

(2)

where $\rho$ is the spectral radius of G.

Lemma 3

For $u,v\in V(G)$ , suppose $G^{\prime }$ is the graph obtained from G by deleting the edges $v{v}_j$ and adding the edges $u{v}_j(1\le j\le t)$ , $x=(x_1,x_2,\dots ,x_n)$ denote the Perron vector of $A(G)$ , where $v_1,\dots ,v_t\in N(v)\backslash N(u)(1\le t\le d(v))$ , and $x_j$ corresponds to the vertex $v_j(1\le j\le n)$ . ⁷ Then, $\rho (G)<\rho (G^{\prime })$ if $x_u\ge x_v$ .

The processes depicted in Lemma 3 are called graft transformation.

Main results

Theorem 1

If G is an unicyclic graph with girth g and k pendant vertices, and $G^{\prime }$ is an unicyclic graph with girth 3 and $k^{\prime }$ pendant vertices, then $\rho (G)<\rho (G^{\prime })$ .

Proof

Assume M is a maximum matching of G. Next we contract the edges in $E(G)-M$ and do the graft transformation process. Then, the girth of G decreases from g to 3, and finally, we obtain the graph $G^{\prime }$ . As is shown in Figure 1, suppose $x=(x_1,x_2,\dots ,x_n)$ is the Perron vector of $A(G)$ in $C_g$ with $x_j$ corresponding to $v_j$ . Next we do the following process to G in the following two cases.

Figure 1.

The transformation from G to G*.

• Case 1: $v_j{v}_{j+1}$ is an edge of a matching in $C_g$

Without loss of generality, suppose $x_j>x_{j+1}$ . Then, $v_{j-1}{v}_j,v_{j+1}{v}_{j+2}\notin E(M)$ . Let $G_1=G-v_{j-1}{v}_j+v_{j-1}{v}_{j+1}$ . Then, by Lemma 3, $\rho (G)<\rho (G_1)$ (Figure 2).

Figure 2.

The transformation from G to G₁ in Case 1.

• Case 2: $v_j{v}_{j+1}\notin E(M)$

Since M is a maximum matching, it contains at least one edge in $\{v_{j-1}{v}_j,v_{j+1}{v}_{j+2}\}$ . We prove Case 2 by the following two subcases (Figure 3).

Figure 3.

The original unicyclic graph in Case 2.

• Subcase 1: Exact one edge of $\{v_{j-1}{v}_j,v_{j+1}{v}_{j+2}\}$ is in $E(M)$

Without loss of generality, suppose $v_{j-1}{v}_j\in E(M),v_{j+1}{v}_{j+2}\notin E(M)$ . Let $G_1=G-v_{j+1}{v}_{j+2}+v_j{v}_{j+2}$ . Thus, $\rho (G)<\rho (G_1)$ by Lemma 3 (Figure 4).

Figure 4.

The transformation from G to G₁ in Subcase 1.

• Subcase 2: $v_{j-1}{v}_j,v_{j+1}{v}_{j+2}\in E(M)$

Because $v_{j-1}{v}_j,v_{j+1}{v}_{j+2}\in E(M)$ , it has $v_{j-2}{v}_{j-1},v_{j+2}{v}_{j+3}\notin E(M)$ . Let $G_1=G-v_{j+2}{v}_{j+3}+v_{j+1}{v}_{j+3}$ . Then, we have $\rho (G)<\rho (G_1)$ by Lemma 3 (Figure 5).

Figure 5.

The transformation from G to G₁ in Subcase 2.

Proceeding by the above cases, the girth of $C_n$ is 3 and finally we obtain $G^{\prime }$ . Thus, $\rho (G)<\rho (G_1)<\cdots <\rho (G^{\prime })$ and then $\rho (G)<\rho (G^{\prime })$ .

Theorem 2

The upper bound of the spectral radius of unicyclic graphs with girth g and k pendant vertices is $1+\sqrt{n-2}$ , namely

$$\rho \le 1+\sqrt{n-2}$$

Proof

By the unicyclic graphs, we know

$$\{\begin{array}{c}T(v_j)-2d(v_j)=n-3\hfill \\ \multicolumn{1}{c}{T(v_k)-2d(v_k)=-n+3}\end{array}$$

(3)

Since for the ith row of A, the sum of all entries is $d(v_j)$ , $S_j(A)=d(v_j)$ . Similarly, $S_j(A^2)=T(v_j)$ . By equation (3), we obtain

$$S_j(A^2)-2S_j(A)\le n-3$$

Suppose $f(x)=x^2-2x$ . By Lemma 2, we have

$${\rho }^2-2\rho \le \underset{j}{max}{S}_j(A^2-2A)=n-3$$

Thus, $\rho \le 1+\sqrt{n-2}$ .

The proof of Theorem 2 is complete.

By the characteristic polynomial of a graph, we can get another upper bound of unicyclic graphs.

Theorem 3

The spectral radius of unicyclic graphs with girth g and k pendant vertices is less than $\sqrt{\frac{n+\sqrt{5n^2-4n+12}}{2}}$ , namely

$$\rho \le \sqrt{\frac{n+\sqrt{5n^2-4n+12}}{2}}$$

Proof

By Lemma 1, we have

$$\begin{array}{c}\Psi (G;\lambda )=\lambda \Psi [P_2\cup (n-3)K_1]-2[(n-2)K_1]\hfill \\ -(n-3)[P_2\cup (n-4)K_1]-2[(n-3)K_1]\hfill \\ =\lambda [({\lambda }^2-1){\lambda }^{n-3}]-2{\lambda }^{n-2}-(n-3)[({\lambda }^2-1){\lambda }^{n-4}]-2{\lambda }^{n-3}\hfill \\ ={\lambda }^n-{\lambda }^{n-2}-2{\lambda }^{n-2}-(n-3){\lambda }^{n-2}+(n-3){\lambda }^{n-4}-2{\lambda }^{n-3}\hfill \\ ={\lambda }^n-n{\lambda }^{n-2}-2{\lambda }^{n-3}+(n-3){\lambda }^{n-4}\hfill \\ ={\lambda }^{n-4}[{\lambda }^4-n{\lambda }^2-2\lambda +(n-3)]\hfill \end{array}$$

Then

$${\lambda }^{n-4}[{\lambda }^4-n{\lambda }^2-2\lambda +(n-3)]=0$$

Calculated

$$\begin{array}{c}{\lambda }_1=0,{\lambda }_2=\sqrt{\frac{n+\sqrt{5n^2-4n+12}}{2}},\hfill \\ {\lambda }_3=-\sqrt{\frac{n+\sqrt{5n^2-4n+12}}{2}}\hfill \\ {\lambda }_4=\sqrt{\frac{n-\sqrt{5n^2-4n+12}}{2}},\hfill \\ {\lambda }_5=-\sqrt{\frac{n-\sqrt{5n^2-4n+12}}{2}}\hfill \end{array}$$

So $\rho \le {\lambda }_2=\sqrt{\frac{n+\sqrt{5n^2-4n+12}}{2}}$ .

Example 1

Figure 6 confirms Theorem 1.

Figure 6.

The examples confirming Theorem 1: (a) $C_{3,8}$ , (b) $C_{4,7}$ , (c) $C_{5,6}$ , (d) $C_{6,5}$ , (e) $C_{7,4}$ , (f) $C_{8,3}$ , (g) $C_{9,2}$ , and (h) $C_{10,1}$ .

According to the graphs in Example 1, we can obtain their adjacency matrixes and then the eigenvalues and spectral radius as follows

$$\begin{array}{l}\rho (C_{3,8})=3.2971,\rho (C_{4,7})=3.1984,\rho (C_{5,6})=2.9835,\\ \rho (C_{6,5})=2.7294,\rho (C_{7,4})=2.5527,\rho (C_{8,3})=2.3761,\\ \rho (C_{9,2})=2.2086,\rho (C_{10,1})=2.0743\end{array}$$

Then $\rho (C_{3,8})>\rho (C_{4,7})>\rho (C_{5,6})>\rho (C_{6,5})>\rho (C_{7,4})>\rho (C_{8,3})>\rho (C_{9,2})>\rho (C_{10,1})$ .

The above results confirm Theorem 1.

Example 2

Compared the size of spectral radius of unicyclic graph in Figure 7.

Figure 7.

The examples of confirming Theorem 3: (a) $C_{3,6}$ , (b) $C_{6,6}$ , (c) $C_{8,6}$ , (d) $C_{10,6}$ , and (e) $C_{12,6}$ .

As Example 1, we can get the spectral radius of the graphs in Examples as follows

$$\begin{array}{l}\rho (C_{3,6})=3.0000,\rho (C_{6,6})=2.8935,\rho (C_{8,6})=2.8866,\\ \rho (C_{10,6})=2.8855,\rho (C_{12,6})=2.8753\end{array}$$

The spectral radius of $C_{3,6}$ is 3, by the calculation, the result of Theorem 2 is 3.64, and the result of Theorem 3 is 3.77, then the results confirm theorems. In this way, the spectral radius of other confirms theorems.

Conclusion

We research on the spectral radius of extremal graphs for the unicyclic graphs with girth g mainly by the graft transformation and matching in this article and obtain the upper bounds of the index of unicyclic graphs by the relations between degree and the second degree. In future, we will focus on the spectral radius of different graphs.