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.

Keywords

Unicyclic graph graft transformation matching spectral radius

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 $Ψ (G)$ . Let $λ_{1} \dots λ_{n}$ denote the eigenvalues of $A (G)$ with $λ_{1} \geq λ_{2} \geq \dots \geq λ_{n}$ , where $λ_{1} \dots λ_{n}$ is called the spectrum of G, and $λ_{1} (G)$ is called the spectral radius of G denoted by $ρ (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} Ψ (G; λ) = λ Ψ (G - v; λ) - \sum_{u - v} Ψ (G - v - u; λ) - 2 \\ \sum_{z \in Z (v)} Ψ (G - V (z); λ) \end{array}

(1)

Lemma 2

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

min_{j} S_{j} (f (A)) \leq f (ρ) \leq max_{j} S_{j} (f (A))

(2)

where $ρ$ is the spectral radius of G.

Lemma 3

For $u, v \in V (G)$ , suppose $G^{'}$ is the graph obtained from G by deleting the edges $v v_{j}$ and adding the edges $u v_{j} (1 \leq j \leq 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) \ N (u) (1 \leq t \leq d (v))$ , and $x_{j}$ corresponds to the vertex $v_{j} (1 \leq j \leq n)$ .⁷ Then, $ρ (G) < ρ (G^{'})$ if $x_{u} \geq 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^{'}$ is an unicyclic graph with girth 3 and $k^{'}$ pendant vertices, then $ρ (G) < ρ (G^{'})$ .

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^{'}$ . 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, $ρ (G) < ρ (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, $ρ (G) < ρ (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 $ρ (G) < ρ (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^{'}$ . Thus, $ρ (G) < ρ (G_{1}) < \dots < ρ (G^{'})$ and then $ρ (G) < ρ (G^{'})$ .

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

ρ \leq 1 + \sqrt{n - 2}

Proof

By the unicyclic graphs, we know

{\begin{matrix} T (v_{j}) - 2 d (v_{j}) = n - 3 \\ T (v_{k}) - 2 d (v_{k}) = - n + 3 \end{matrix}

(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}) - 2 S_{j} (A) \leq n - 3

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

ρ^{2} - 2 ρ \leq max_{j} S_{j} (A^{2} - 2 A) = n - 3

Thus, $ρ \leq 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{5 n^{2} - 4 n + 12}}{2}}$ , namely

ρ \leq \sqrt{\frac{n + \sqrt{5 n^{2} - 4 n + 12}}{2}}

Proof

By Lemma 1, we have

\begin{matrix} Ψ (G; λ) = λ Ψ [P_{2} \cup (n - 3) K_{1}] - 2 [(n - 2) K_{1}] \\ - (n - 3) [P_{2} \cup (n - 4) K_{1}] - 2 [(n - 3) K_{1}] \\ = λ [(λ^{2} - 1) λ^{n - 3}] - 2 λ^{n - 2} - (n - 3) [(λ^{2} - 1) λ^{n - 4}] - 2 λ^{n - 3} \\ = λ^{n} - λ^{n - 2} - 2 λ^{n - 2} - (n - 3) λ^{n - 2} + (n - 3) λ^{n - 4} - 2 λ^{n - 3} \\ = λ^{n} - n λ^{n - 2} - 2 λ^{n - 3} + (n - 3) λ^{n - 4} \\ = λ^{n - 4} [λ^{4} - n λ^{2} - 2 λ + (n - 3)] \end{matrix}

Then

λ^{n - 4} [λ^{4} - n λ^{2} - 2 λ + (n - 3)] = 0

Calculated

\begin{matrix} λ_{1} = 0, λ_{2} = \sqrt{\frac{n + \sqrt{5 n^{2} - 4 n + 12}}{2}}, \\ λ_{3} = - \sqrt{\frac{n + \sqrt{5 n^{2} - 4 n + 12}}{2}} \\ λ_{4} = \sqrt{\frac{n - \sqrt{5 n^{2} - 4 n + 12}}{2}}, \\ λ_{5} = - \sqrt{\frac{n - \sqrt{5 n^{2} - 4 n + 12}}{2}} \end{matrix}

So $ρ \leq λ_{2} = \sqrt{\frac{n + \sqrt{5 n^{2} - 4 n + 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} ρ (C_{3, 8}) = 3.2971, ρ (C_{4, 7}) = 3.1984, ρ (C_{5, 6}) = 2.9835, \\ ρ (C_{6, 5}) = 2.7294, ρ (C_{7, 4}) = 2.5527, ρ (C_{8, 3}) = 2.3761, \\ ρ (C_{9, 2}) = 2.2086, ρ (C_{10, 1}) = 2.0743 \end{array}

Then $ρ (C_{3, 8}) > ρ (C_{4, 7}) > ρ (C_{5, 6}) > ρ (C_{6, 5}) > ρ (C_{7, 4}) > ρ (C_{8, 3}) > ρ (C_{9, 2}) > ρ (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} ρ (C_{3, 6}) = 3.0000, ρ (C_{6, 6}) = 2.8935, ρ (C_{8, 6}) = 2.8866, \\ ρ (C_{10, 6}) = 2.8855, ρ (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.

Footnotes

Academic Editor: Hamid Reza Karimi

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by the National Natural Science Foundation of China (61473139, 11426125, and 61622303), the project for Distinguished Professor of Liaoning Province.

References

Karimi

Shi

Dissipativity-based small-gain theorems for stochastic network systems. IEEE T Automat Contr 2016; 61: 2065–2078.

Tang

Xing

Karimi

. Tracking control of networked multi-agent systems under new characterizations of impulses and its applications in robotic systems. IEEE T Ind Electron 2016; 63: 1299–1307.

Chen

Sun

. Stabilization for a class of nonlinear networked control systems via polynomial fuzzy model approach. Complexity 2015; 21: 74–81.

Liu

Tong

. Neural approximation-based adaptive control for a class of nonlinear nonstrict feedback discrete-time systems. IEEE T Neural Networ Learn Syst. Epub ahead of print 8 March 2016. DOI: 10.1109/TNNLS.2016.2531089.

Liu

Tong

Barrier Lyapunov functions for Nussbaum gain adaptive control of full state constrained nonlinear systems. Automatica 2017; 76: 143–152.

Liu

Tong

Chen

CLP

. Adaptive NN control using integral barrier Lyapunov functionals for uncertain nonlinear block-triangular constraint systems. IEEE T Cybern. Epub ahead of print 19 September 2016. DOI: 10.1109/TCYB.2016.2581173.

Liu

Tong

SC.

Optimal control-based adaptive NN design for a class of nonlinear discrete-time block-triangular systems. IEEE T Cybern 2016; 46: 2670–2680.

Liu

Tong

. Neural network control-based adaptive learning design for nonlinear systems with full state constraints. IEEE T Neural Networ Learn Syst 2016; 27: 1562–1571.

Wen

Chen

CLP

Liu

. Neural network-based adaptive leader-following consensus control for a class of nonlinear multiagent state-delay systems. IEEE T Cybern. Epub ahead of print 11 October 2016. DOI: 10.1109/TCYB.2016.2608499.

10.

Xiao

Yuan

The spectral radius of trees on k pendant vertices. Linear Algebra Appl 2005; 395: 342–349.

11.

Elingham

Zha

The spectral radius of graphs on surface. J Combin Theory Series B 2000; 78: 45–56.

12.

Wang

Zhai

MQ.

Upper bounds on the spectral radius of k trees. Applied Math 2011; 26: 209–214.

13.

Yuan

Shu

JL.

A new upper bound for the spectral radius of Halin graphs and the extremal graphs. Applied Mathematics 2008; 23: 335–342.

14.

Fan

Zhang

Wang

YS.

Spectral radii of unicyclic graphs with fixed number of cut vertices. Discrete Math Algorithm Appl 2011; 3: 139–145.

15.

Belardo

Li Marzi

Simic

. On the spectral radius of unicyclic graphs with prescribed degree sequence. Linear Algebra Appl 2011; 43: 2323–2334.

16.

Hong

On the spectra of unicyclic graphs. J East China Normal Univ 1986; 37: 31–34.

17.

Pedersen

Vestergaard

PD.

The number of independent sets in unicyclic graphs. Discrete Appl Math 2005; 15: 246–256.

18.

Liu

Mei

Tian

On the spectral radius of unicyclic graphs with fixed diameter. Linear Algebra Appl 2007; 56: 449–457.

19.

Zhou

Sharp upper bounds for the Laplacian spectral radius of graphs. Math Probl Eng 2013; 2013: 720854 (4 pp.).

20.

Feng

On the largest eigenvalue of graphs. Acta Math Appl Sin 1979; 43: 167–175.

21.

Hou

JS.

Bounds on the largest eigenvalues of trees with a given size of matching. Linear Algebra Appl 2002; 31: 203–217.

22.

Mao

Chen

. The spectral radius for a class of double-star-like tree systems with maximal degree 4. Math Probl Eng 2015; 2015: 529024 (6 pp.).

23.

Liu

BL.

Combinatorial matrix theory. Beijing, China: Science Press, 2005.