PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 97(111) (2015), 187–197 DOI: 10.2298/PIM140921001Z

ON THE SIGNLESS LAPLACIAN SPECTRAL RADIUS OF UNICYCLIC GRAPHS WITH FIXED MATCHING NUMBER

Jing-Ming Zhang, Ting-Zhu Huang, and Ji-Ming Guo

Abstract. We determine the graph with the largest signless Laplacian spectral radius among all unicyclic graphs with fixed matching number.

1. Introduction

Let G = (V (G), E(G)) be a simple connected graph with vertex set V (G) = {v_{1}, v_{2}, …, v_{n}} and edge set E(G). Its adjacency matrix A(G) = (a_{ij} ) is defined as an n × n matrix (a_{ij} ), where a_{ij} = 1 if v_{i} is adjacent to v_{j}; a_{ij} = 0, otherwise. Denote by d(v_{i}) or d_{G}(v_{i}) the degree of the vertex v_{i} (i = 1, 2, …, n). Let Q(G) = D(G) + A(G) be the signless Laplacian matrix of a graph G, where D(G) = diag(d(v_{1}), d(v_{2}), …, d(v_{n})) denotes the diagonal matrix of the vertex degrees of G. It is well known that A(G) is a real symmetric matrix and Q(G) is a positive semidefinite matrix. Hence, the eigenvalues of A(G) and Q(G) can be ordered as

λ_{1}(G) ⩾ λ_{2}(G) ⩾ ⋯⩾ λ_{n}(G)

and

q_{1}(G) ⩾ q_{2}(G) ⩾ ⋯⩾ q_{n}(G) ⩾ 0,

respectively. The largest eigenvalues of A(G) and Q(G) are called the spectral radius and the signless Laplacian spectral radius of G, denoted by ρ(G) and q(G), respectively. When G is connected, A(G) and Q(G) are nonegative irreducible matrix. By the Perron–Frobenius theory, ρ(G) is simple and has a unique positive unit eigenvector, so does q(G). We refer to such the eigenvector corresponding to q(G) as the Perron vector of G.

Two distinct edges in a graph G are independent if they are not adjacent in G. A set of pairwise independent edges of G is called a matching in G. A matching of maximum cardinality is a maximum matching in G. The cardinality of a maximum matching of G is commonly known as its matching number, denoted by μ(G).

2010 Mathematics Subject Classification: 05C50.

Key words and phrases: unicyclic graph; signless Laplacian spectral radius; matching number.

Partially supported by NSFC (Nos. 11371372, 61370147, and 61170309) and Chinese Universities Specialized Research Fund for the Doctoral Program (20110185110020).

Communicated by Sobodan Simić.

Denote by C_{n} and P_{n} the cycle and the path on n vertices, respectively. The characteristic polynomial of A(G) is det(xI − A(G)), which is denoted by Φ(G) or Φ(G, x). The characteristic polynomial of Q(G) is det(xI −Q(G)), which is denoted by Ψ(G) or Ψ(G, x).

A unicyclic graph is a connected graph in which the number of vertices equals the number of edges. Let U_{n}(μ) denote the set of all unicyclic graphs on n vertices with matching number μ.

The investigation on the spectral radius of graphs is an important topic in the theory of graph spectra, and some early results can go back to the very beginnings (see [4]). The recent developments on this topic also involve the problem concerning graphs with maximal or minimal spectral radius of a given class of graphs. In [2], Chang et al. gave the first two spectral radii of unicyclic graphs with perfect matchings. Recently, Yu et al. [9] gave the first two spectral radii of unicyclic graphs with a given matching number; and Guo [13] gave the first six spectral radii over the class of unicyclic graphs on a given number of vertices; Guo [12] gave the first ten spectral radii over the class of unicyclic graphs on a given number of vertices and the first four spectral radii of unicyclic graphs with perfect matchings. For more results on this topic, the reader is referred to [1, 6, 14, 3] and the references therein.

In this paper, we deal with the extremal signless Laplacian spectral radius problems for the unicyclic graphs with fixed matching number. The graph with the largest signless Laplacian spectral radius among all unicyclic graphs with a fixed matching number is obtained.

2. Lemmas

Let G − u or G − uv denote the graph obtained from G by deleting the vertex u ∈ V (G) or the edge uv ∈ E(G). A pendant vertex of G is a vertex with degree one. A path P : vv_{1}v_{2} ⋯ v_{k} in G is called a pendant path if d(v_{1}) = d(v_{2}) = ⋯= d(v_{k−1} ) = 2 and d(v_{k}) = 1. If k = 1, then we say vv_{1} is a pendant edge of the graph G.

In order to complete the proof of our main result, we need the following lemmas.

Lemma 2.1. [7, 15] Let G be a connected graph, and u, v be two vertices of G. Suppose that v_{1}, v_{2}, …, v_{s} ∈ N(v)\{N(u) ∪ u} (1 ⩽ s ⩽ d(v)) and x = (x_{1}, x_{2}, …, x_{n}) is the Perron vector of G, where x_{i} corresponds to the vertex v_{i} (1 ⩽ i ⩽ n). Let G^{∗} be the graph obtained from G by deleting the edges vv_{i} and adding the edges uv_{i}(1 ⩽ i ⩽ s). If x_{u} ⩾ x_{v}, then q(G) < q(G^{∗}).

From Lemma 2.1, we obtain the following results.

Corollary 2.1. Let G = (V, E) be a connected graph with vertex set V = {v_{1}, v_{2}, …, v_{n}}. Suppose that v_{1}v_{2} is an edge of G which does not lie on a circuit of length three satisfying d(v_{1}) ⩾ 2 and d(v_{2}) ⩾ 2. Let G̃ be the graph obtained from G − v_{1}v_{2} by amalgamating v_{1} and v_{2} to form a new vertex w_{1} together with attaching a new pendant vertex w_{2} to w_{1}. Then q(G̃) > q(G).

Corollary 2.2. Let w and v be two vertices in a connected graph G and suppose that s paths {ww_{1}w′_{1}, ww_{2}w′_{2}, …, ww_{s}w′_{s}} of length 2 are attached to G at w and t paths {vv_{1}v′_{1}, vv_{2}v′_{2}, …, vv_{t}v′_{t}} of length 2 are attached to G at v to form G_{s,t}. Then either q(G_{s+i,t−i} ) > q(G_{s,t}) (1 ⩽ i ⩽ t), or q(G_{s−i,t+i} ) > q(G_{s,t}) (1 ⩽ i ⩽ s) and μ(G_{0,s+t} ) = μ(G_{s+t,0} ) = μ(G_{s,t}).

Corollary 2.3. Let w and v be two vertices in a connected graph G and suppose that s paths {ww_{1}, ww_{2}, …, ww_{s}} of length 1 are attached to G at w and t paths {vv_{1}v′_{1}, vv_{2}v′_{2}, …, vv_{t}v′_{t}} of length 2 are attached to G at v to form H_{s,t}. Then either

q(H_{s,t} − ww_{1} − ⋯− ww_{i} + vw_{1} + ⋯+ vw_{i}) > q(H_{s,t}) (1 ⩽ i ⩽ s) or q(H_{s,t} − vv_{1} − ⋯− vv_{i} + wv_{1} + ⋯+ wv_{i}) > q(H_{s,t}) (1 ⩽ i ⩽ t).

Corollary 2.4. Let w and v be two vertices in a connected graph G and suppose that s paths {ww_{1}, ww_{2}, …, ww_{s}} of length 1 are attached to G at w and t paths {vv_{1}, vv_{2}, …, vv_{t}} of length 1 are attached to G at v to form F_{s,t}. Then either

q(F_{s+i,t−i} ) > q(F_{s,t}) (1 ⩽ i ⩽ t), or q(F_{s−i,t+i} ) > q(F_{s,t}) (1 ⩽ i ⩽ s).

Corollary 2.5. Suppose u is a vertex of graph G with d(u) ⩾ 2. Let G : uv be a graph obtained by attaching a pendant edge uv to G at u. Suppose t paths {vv_{1}v′_{1}, …, vv_{t}v′_{t}} of length 2 are attached to G : uv at v to form L_{0,t}. Let

M_{1,t} = L_{0,t} − vv_{1} − ⋯− vv_{t} + uv_{1} + ⋯+ uv_{t}.

Then we have μ(M_{1,t}) = μ(L_{0,t}) and q(M_{1,t}) > q(L_{0,t}), (t ⩾ 1).

An internal path of a graph G is a sequence of vertices v_{1}, v_{2}, …, v_{m} with m ⩾ 2 such that:

(1) The vertices in the sequences are distinct (except possibly v_{1} = v_{m});

(2) v_{i} is adjacent to v_{i+1} , (i = 1, 2, …, m − 1);

(3) The vertex degrees d(v_{i}) satisfy d(v_{1}) ⩾ 3, d(v_{2}) = ⋯= d(v_{m−1} ) = 2 (unless m = 2) and d(v_{m}) ⩾ 3.

Lemma 2.2. Suppose that P : v_{1}v_{2} ⋯ v_{k} (k ⩾ 3) is an internal path of the graph G and v_{1}v_{k} ∉ E(G) for k = 3. Let G^{∗} be the graph obtained from G − v_{i}v_{i+1} − v_{i+1} v_{i+2} (1 ⩽ i ⩽ k − 2) by amalgamating v_{i}, v_{i+1} and v_{i+2} to form a new vertex w_{1} together with attaching a new pendant path w_{1}w_{2}w_{3} of length 2 at w_{1}. Then q(G^{∗}) > q(G) and μ(G^{∗}) = μ(G).

Proof. Let G′ = G^{∗} − w_{2} − w_{3}. By similar reasoning as that of Theorem 3.1 of [11] and Theorem 4.11 of [10], we have q(G′) > q(G). From the well-known Perron–Frobenius theory, we have q(G^{∗}) > q(G′). Thus we have q(G^{∗}) > q(G). Next,we prove μ(G^{∗}) ⩾ μ(G). Let M be a maximum matching of G. If v_{i}v_{i+1} ∈ M or v_{i+1} v_{i+2} ∈ M, then {M − {v_{i}v_{i+1} }} ∪ {w_{2}w_{3}} or {M − {v_{i+1} v_{i+2} }} ∪ {w_{2}w_{3}} is a matching of G^{∗}. Thus, μ(G^{∗}) ⩾ μ(G); if v_{i}v_{i+1} ∉ M and v_{i+1} v_{i+2} ∉ M, then there exist two edges v_{i}u and v_{i+2} v ∈ M. Thus, {M − {v_{i}u}} ∪ {w_{2}w_{3}} is a matching of G^{∗}. Hence, μ(G^{∗}) ⩾ μ(G). Let M_{0} be a maximum matching of G^{∗}. If there exists some vertex, say u(≠ w_{2}), of G^{∗} such that uw_{1} ∈ M_{0}, then w_{2}w_{3} ∈ M_{0}. Thus {M_{0} − {uw_{1}, w_{2}w_{3}}} ∪ {uv_{i}, v_{i+1} v_{i+2} } is a matching of G; if there’s no such a vertex, then we have either w_{1}w_{2} ∈ M_{0} or w_{2}w_{3} ∈ M_{0}. Thus {M_{0} − {w_{1}w_{2}, w_{2}w_{3}}} ∪ {v_{i+1} v_{i+2} } is a matching of G. So, μ(G) ⩾ μ(G^{∗}). Hence, μ(G) = μ(G^{∗}). □

Let S(G) be the subdivision graph of G obtained by subdividing every edge of G.

Lemma 2.3. [5, 18] Let G be a graph on n vertices and m edges. Then Φ(S(G)) = x^{m−n} Ψ(G, x^{2}), where Φ(G) and Ψ(G) are the characteristic polynomials of A(G) and Q(G), respectively.

Lemma 2.4. [8] Let u be a vertex of a connected graph G with at least two vertices. Let G_{k,l} (k, l ⩾ 0) be the graph obtained from G by attaching two pendant paths of lengths k and l at u, respectively. If k ⩾ l ⩾ 1, then q(G_{k,l}) > q(G_{k+1,l−1} ).

Corollary 2.6. Suppose that P : v_{1}v_{2} ⋯ v_{k} (k ⩾ 4) is a pendant path of the graph G with d(v_{1}) ⩾ 3. Let G^{∗} = G − v_{k−2} v_{k−1} + v_{1}v_{k−1} . Then q(G^{∗}) > q(G) and μ(G^{∗}) = μ(G).

Proof. By Lemma 2.4, we have q(G^{∗}) > q(G). By similar reasoning as that of Lemma 2.2, we have μ(G^{∗}) = μ(G). □

Lemma 2.5. [17] Let e = uv be an edge of G, and C(e) be the set of all circuits containing e. Then Φ(G) satisfies

Φ(G) = Φ(G − e) − Φ(G − u − v) − 2 ∑_{Z} Φ(G − V (Z)),

where the summation extends over all Z ∈ C(e).

From the Perron–Frobenius theory, we immediately have the following

Lemma 2.6. (1) Let △(G) be the maximum degree of G. Then ρ(G) ⩾ \sqrt{△(G)} .

(2) Let G be a connected graph, and let G′ be a proper spanning subgraph of G. Then ρ(G) > ρ(G′) and q(G) > q(G′).

3. Main results

Theorem 3.1. Let G = (V, E) be a connected graph with n ⩾ 4 vertices. Suppose that v_{1}v_{2} ∈ E(G), v_{1}v_{3} ∈ E(G), v_{1}v_{4} ∈ E(G), d(v_{3}) ⩾ 2, d(v_{4}) ⩾ 2, d(v_{1}) = 3, and d(v_{2}) = 1. Let G_{v_{1} v_{3}} (G_{v_{1} v_{4}} ) be the graph obtained from G − v_{1}v_{3} (G − v_{1}v_{4}) by amalgamating v_{1} and v_{3} (v_{4}) to form a new vertex w_{1} (w_{3}) together with subdivising the edge w_{1}v_{2} (w_{3}v_{2}) with a new vertex w_{2}(w_{4}). If q = q(G) > 3 + \sqrt{5} ≈ 5.23606, then

(1) either q(G_{v_{1} v_{3}} ) > q(G) or q(G_{v_{1} v_{4}} ) > q(G);

(2) μ(G_{v_{1} v_{3}} ) ⩾ μ(G) and μ(G_{v_{1} v_{4}} ) ⩾ μ(G).

Proof. Let X = (x_{1}, x_{2}, …, x_{n})^{T} be the Perron vector of G. Then from (D(G) + A(G))X = q(G)X, we have

(3.1)  qx_{i} = d_{i}x_{i} + ∑_{v_{i} v_{j} ∈E} x_{j} .

We distinguish the following two cases:

Case 1: x_{3} ⩾ x_{4}. From (3.1), we have
(3.2)  x_{1} = (q − 1)x_{2},
(3.3)  qx_{1} = 3x_{1} + x_{2} + x_{3} + x_{4}.

Substituting (3.2) into (3.3), together with condition x_{3} ⩾ x_{4}, we get

(3.4)  ( q − 3 − \frac{1}{q − 1} ) x_{1} ⩽ 2x_{3}.

From (3.4), we have if q−3−\frac{1}{q−1} > 2, namely, q(G) > 3+\sqrt{5}, then x_{3} > x_{1}. Suppose that the vertices w_{1}, w_{2}, v_{2}, v_{4}, …, v_{n} of G_{v_{1} v_{3}} are relabelled v_{3}, v_{1}, v_{2}, v_{4}, …, v_{n}, respectively. Then

X^{T}Q(G_{v_{1} v_{3}} )X −q(G) = X^{T}Q(G_{v_{1} v_{3}} )X −X^{T}Q(G)X = x_{3}^{2} −x_{1}^{2} +2x_{4}(x_{3} −x_{1}) > 0.

Thus q(G_{v_{1} v_{3}} ) > q(G).

Case 2: x_{4} > x_{3}. By similar reasoning as that of Case 1, we have q(G_{v_{1} v_{4}} ) > q(G).

Now, we prove that (2) holds. Let M be a maximum matching of G. If v_{1}v_{3} ∈ M, then {M − v_{1}v_{3}} ∪ {v_{2}w_{2}} is a matching of G_{v_{1} v_{3}} . So, μ(G_{v_{1} v_{3}} ) ⩾ μ(G). If v_{1}v_{3} ∉ M, then v_{1}v_{2} ∈ M or v_{1}v_{4} ∈ M. So {M − v_{1}v_{2} − v_{1}v_{4}} ∪ {v_{2}w_{2}} is also a matching of G_{v_{1} v_{3}} . Thus, μ(G_{v_{1} v_{3}} ) ⩾ μ(G). By similar reasoning, we have μ(G_{v_{1} v_{4}} ) ⩾ μ(G). □

Figure 1. G_{1} − G_{4}

Lemma 3.1. Let G_{1}, G_{2} and G_{3} be the graphs as given in Figure 1. Then for n ⩾ 6, we have q(G_{1}) > q(G_{2}), q(G_{1}) > q(G_{3}).

Proof. From Lemma 2.1, it is easy to see that q(G_{1}) > q(G_{2}). Now we prove that q(G_{1}) > q(G_{3}). From Lemma 2.5, we have

(3.5) Φ(S(G_{3})) − Φ(S(G_{1})) = x^{2}(x^{2} − 1)^{n−2μ} (x^{4} − 3x^{2} + 1)^{μ−4} [(n − μ − 3)x^{10}
+ (20 + 6μ − 6n)x^{8} + (11n − 49 − 10μ)x^{6}
+ (54 − 6n + 3μ)x^{4} + (n − 25)x^{2} + 4].
If n ⩾ 10, it is easy to prove that for x ⩾ \sqrt{n − μ + 1} , x^{2}−1 > 0, x^{4}−3x^{2}+1 > 0

and (n − μ − 3)x^{10} + (20 + 6μ − 6n)x^{8} + (11n − 49 − 10μ)x^{6} + (54 − 6n + 3μ)x^{4} + (n − 25)x^{2} + 4 > 0. By Lemma 2.6, we know that ρ(S(G_{1})) ⩾ \sqrt{n − μ + 1} . Thus, ρ(S(G_{1})) > ρ(S(G_{3})) (n ⩾ 10). For 6 ⩽ n ⩽ 9, by direct calculation, we have ρ(S(G_{1})) > ρ(S(G_{3})). By Lemma 2.3, we have q(G_{1}) > q(G_{3}). □

Theorem 3.2. Suppose u is a vertex of the unicyclic graph G with d(u) ⩾ 2. Let G : uv be a graph obtained by attaching a pendant edge uv to G at u. Suppose that s paths {vw_{1}, …, vw_{s}} of length 1 and t paths {vv_{1}v′_{1}, …, vv_{t}v′_{t}} of length 2 are attached to G : uv at v to form L_{s,t}. Let M_{s−1,t+1} = L_{s,t} − vv_{1} − ⋯− vv_{t} − vw_{1} − ⋯− vw_{s−1} + uv_{1} + ⋯+ uv_{t} + uw_{1} + ⋯+ uw_{s−1} . Then we have

(1) q(M_{s−1,t+1} ) > q(L_{s,t}), (s ⩾ 2 or t ⩾ 1);

(2) μ(L_{0,t}) = μ(M_{−1,t+1} ) and μ(L_{s,t}) ⩽ μ(M_{s−1,t+1} ), (s ⩾ 1).

Proof. We distinguish the following four cases:

Case 1: s = 0, t ⩾ 1. Then we have M_{s−1,t+1} = M_{−1,t+1} and L_{s,t} = L_{0,t}.

Since M_{−1,t+1} (t ⩾ 1) can also be obtained from L_{0,t} by identifying u and v with subsequent removal of the loop, and adding a new pendant edge at this new vertex, it is easy to show that μ(M_{−1,t+1} ) = μ(L_{0,t}) and from Corollary 2.1, we have q(M_{−1,t+1} ) > q(L_{0,t}), (t ⩾ 1).

Case 2: s ⩾ 2, t ⩾ 1. Suppose a new pendant edge vw is attached to G : uv at v to form G : uvw. And then we subdivide every edge of G in G : uvw to obtain the graph S(G) : uvw.

Suppose that s paths {ww_{1}w′_{1}, …, ww_{s}w′_{s}} of length 2 and t paths

{ww_{11}w_{12}w_{13}w_{14}, …, ww_{t1}w_{t2}w_{t3}w_{t4}}

of length 4 are attached to S(G) : uvw at w to form L̄_{s,t} . Let

M̄_{s−1,t+1} = L̄_{s,t} − ww_{1} − ⋯− ww_{s−1} − ww_{11} − ⋯− ww_{t1}
+ uw_{1} + ⋯+ uw_{s−1} + uw_{11} + ⋯+ uw_{t1} .

Obviously, M̄_{s−1,t+1} ≅ S(M_{s−1,t+1} ), L̄_{s,t} ≅ S(L_{s,t}) and M̄_{0,1} ≅ L̄_{1,0} .

By Lemma 2.3, we only need to prove that ρ(M̄_{s−1,t+1} ) > ρ(L̄_{s,t} ). Obviously, P_{4} is a proper subgraph of S(L_{1,t}). From Lemma 2.6, we have ρ(S(L_{1,t})) > ρ(S(G) − u) > ρ(P_{4}) ≈ 1.61803 > \sqrt{2}.

ON THE SIGNLESS LAPLACIAN SPECTRAL RADIUS OF UNICYCLIC GRAPHS 193

From Lemma 2.5, we have

Φ(L̄_{s,t} ) = Φ(L̄_{s,t} − ww_{1}) − Φ(L̄_{s,t} − w − w_{1})
= (x^{2}− 1)Φ(L̄_{s−1,t} ) − x(x^{2}− 1)^{s−1} (x^{4}− 3x^{2}+ 1)^{t}Φ(S(G) : uv)

⋯ (3.6)

= (x^{2} − 1)^{s−1} Φ(L̄_{1,t}) − (s − 1)x(x^{2} − 1)^{s−1} (x^{4} − 3x^{2} + 1)^{t}Φ(S(G) : uv),

and

(3.7)  Φ(L̄_{1,t}) = Φ(L̄_{1,t} − ww_{11}) − Φ(L̄_{1,t} − w − w_{11})
= (x^{4} − 3x^{2} + 1)Φ(L̄_{1,t−1} ) − (x^{2} − 1)(x^{3} − 2x)
· (x^{4} − 3x^{2} + 1)^{t−1} Φ(S(G) : uv)
⋯
= (x^{4} − 3x^{2} + 1)^{t}Φ(L̄_{1,0} ) − t(x^{2} − 1)(x^{3} − 2x)
· (x^{4} − 3x^{2} + 1)^{t−1} Φ(S(G) : uv).

Substituting (3.7) into (3.6), we have

(3.8)  Φ(L̄_{s,t} ) = (x^{2} − 1)^{s−1} (x^{4} − 3x^{2} + 1)^{t}Φ(L̄_{1,0} )

− t(x^{3} − 2x)(x^{2} − 1)^{s}(x^{4} − 3x^{2} + 1)^{t−1} Φ(S(G) : uv) − (s − 1)x(x^{2} − 1)^{s−1} (x^{4} − 3x^{2} + 1)^{t}Φ(S(G) : uv),

(3.9)  Φ(M̄_{s−1,t+1} ) = Φ(M̄_{s−1,t+1} − uw_{1}) − Φ(M̄_{s−1,t+1} − u − w_{1})
= (x^{2} − 1)Φ(M̄_{s−2,t+1} ) − x(x^{2} − 1)^{s−2}

· (x^{4} − 3x^{2} + 1)^{t+1} Φ(S(G) − u)

⋯

= (x^{2} − 1)^{s−1} Φ(M̄_{0,t+1} ) − (s − 1)x(x^{2} − 1)^{s−2}

· (x^{4} − 3x^{2} + 1)^{t+1} Φ(S(G) − u),

(3.10)  Φ(M̄_{0,t+1} ) = Φ(M̄_{0,t+1} − uw_{11}) − Φ(M̄_{0,t+1} − u − w_{11})

= (x^{4} − 3x^{2} + 1)Φ(M̄_{0,t}) − (x^{3} − 2x)(x^{4} − 3x^{2} + 1)^{t}

· Φ(S(G) − u)
⋯

= (x^{4} − 3x^{2} + 1)^{t}Φ(M̄_{0,1} ) − t(x^{3} − 2x)(x^{4} − 3x^{2} + 1)^{t}

· Φ(S(G) − u).

Substituting (3.10) into (3.9), we have

(3.11) Φ(M̄_{s−1,t+1} ) = (x^{2} − 1)^{s−1} (x^{4} − 3x^{2} + 1)^{t}Φ(M̄_{0,1} )

− t(x^{3} − 2x)(x^{2} − 1)^{s−1} (x^{4} − 3x^{2} + 1)^{t}Φ(S(G) − u) − (s − 1)x(x^{2} − 1)^{s−2} (x^{4} − 3x^{2} + 1)^{t+1} Φ(S(G) − u).

194 ZHANG, HUANG, AND GUO

From (3.8) and (3.11), we have Φ(L̄_{s,t} ) − Φ(M̄_{s−1,t+1} ) (3.12)

= [t(x^{3} − 2x)(x^{2} − 1)^{s−1} (x^{4} − 3x^{2} + 1)^{t−1} + (s − 1)x(x^{2} − 1)^{s−2}
· (x^{4} − 3x^{2} + 1)^{t}][(x^{4} − 3x^{2} + 1)Φ(S(G) − u) − (x^{2} − 1)Φ(S(G) : uv)].

From Lemma 2.5, by simple calculation, we have (x^{4} − 3x^{2} + 1)Φ(S(G) − u) − (x^{2} − 1)Φ(S(G) : uv) (3.13)

= −x^{2}Φ(S(G) − u) + x(x^{2} − 1) ∑_{y} Φ(S(G) − u − y)

+ 2x(x^{2} − 1) ∑_{Z} Φ(S(G) − Z) .

Since d_{G}(u) ⩾ 2 and S(G) is the subdivision graph of G, we have d_{S(G)} (u) ⩾ 2. Without loss of generality, we can suppose that y_{1} and y_{2} are two vertices of S(G) such that y_{i}u ∈ E(S(G)) (i = 1, 2). For x > ρ(S(G) − u), we have from (3.13) that (x^{4} − 3x^{2} + 1)Φ(S(G) − u) − (x^{2} − 1)Φ(S(G) : uv) (3.14)

⩾ −x^{2}Φ(S(G) − u) + x(x^{2} − 1)[Φ(S(G) − u − y_{1}) + Φ(S(G) − u − y_{2})]

and from [16], we have

(3.15)  xΦ(S(G) − u − y_{i}) > Φ(S(G) − u) > 0, (i = 1, 2).

Since x > ρ(S(G) − u) > \sqrt{2}, we have 2(x^{2} − 1) > x^{2}. Hence, we have from (3.15) that for x > ρ(S(G) − u),

−x^{2}Φ(S(G) − u) + x(x^{2} − 1)[Φ(S(G) − u − y_{1}) + Φ(S(G) − u − y_{2})] > 0. So, from (3.14), we have for x > ρ(S(G) − u),

(x^{4} − 3x^{2} + 1)Φ(S(G) − u) − (x^{2} − 1)Φ(S(G) : uv) > 0.

Combined with (3.12), we have for x > ρ(S(G) − u), Φ(L̄_{s,t} ) − Φ(M̄_{s−1,t+1} ) > 0. Since ρ(L̄_{s,t} ) > ρ(S(G)−u), we have ρ(M̄_{s−1,t+1} ) > ρ(L̄_{1,t}). Hence, q(M_{s−1,t+1} ) > q(L_{s,t}) by Lemma 2.3.

Case 3: s = 1, t ⩾ 1. Then we have M̄_{s−1,t+1} = M̄_{0,t+1} , L̄_{s,t} = L̄_{1,t}. From (3.7) and (3.10), we have

Φ(L̄_{1,t}) − Φ(M̄_{0,t+1} ) = t(x^{3} − 2x)(x^{4} − 3x^{2} + 1)^{t−1}
[(x^{4} − 3x^{2} + 1)Φ(S(G) − u) − (x^{2} − 1)Φ(S(G) : uv)].

By the similar reasoning as that of Case 2, we have q(M_{0,t+1} ) > q(L_{1,t}).

Case 4: s ⩾ 2, t = 0. Then we have M̄_{s−1,t+1} = M̄_{s−1,1} and L̄_{s,t} = L̄_{s,0} . From (3.6) and (3.9), we have

Φ(L̄_{s,0} ) − Φ(M̄_{s−1,1} ) = (s − 1)x(x^{2} − 1)^{s−2}
· [(x^{4} − 3x^{2} + 1)Φ(S(G) − u) − (x^{2} − 1)Φ(S(G) : uv)].

By the similar reasoning as that of Case 2, we have q(M_{s−1,1} ) > q(L_{s,0} ).

In the end, we prove that μ(L_{s,t}) ⩽ μ(M_{s−1,t+1} ) for s ⩾ 1. Let M be a maximum matching of L_{s,t}. If uv ∈ M, then {M − {uv}} ∪ {vw_{s}} is a matching of M_{s−1,t+1} . So, μ(L_{s,t}) ⩽ μ(M_{s−1,t+1} ). If uv ∉ M, then there exists some edge, say vw_{s}, of L_{s,t} such that vw_{s} ∈ M. Then M is also a matching of M_{s−1,t+1} . Thus, μ(L_{s,t}) ⩽ μ(M_{s−1,t+1} ). □

The length of the shortest path between vertices u and v is defined as the distance of u and v, denoted by d(u, v). Let G_{1}, G_{2}, G_{3} and G_{4} be the graphs as Figure 1. Let B, \overline{G}_{1}, \overline{G}_{2} and \overline{G}_{3} be the graphs as given in Figure 2.

Figure 2. \overline{G}_{1} − \overline{G}_{3}, B

Denote by U_{n}^{g}(μ) the set of all unicyclic graphs on n vertices with matching number μ and girth g (⩾ 3).

Theorem 3.3. If G ∈ U_{n}(μ), (n ⩾ 6), then q(G) ⩽ q(G_{1}), with equality if and only if G = G_{1}.

Proof. Let X = (x_{1}, x_{2}, …, x_{n})^{T} be the Perron vector of G. From Lemma 2.6 and by direct calculations, we have for μ ⩾ 3, q(G_{1}) ⩾ q(B) ≈ 5.38 > 3 + \sqrt{5} > 4 ⩾ q(C_{n}). So, in the following, we can suppose that q(G) > 3 + \sqrt{5} and G ≠ C_{n}.

Choose G^{∗} ∈ U_{n}(μ) such that q(G^{∗}) is as large as possible. Then G^{∗} consists of a cycle C_{g} (g ⩾ 3) as a subgraph. Let T be a tree attached at some vertex, say z, of C_{g}, |V (T)| is the number of vertices of T including the vertex z. In the following, we prove that T is formed by attaching paths of length at most 2 at z.

Suppose that P : v_{0}v_{1} …v_{k} is a pendant path of G^{∗} and v_{k} is a pendant vertex. If k ⩾ 3, let H_{1} = G^{∗}−v_{k−2} v_{k−1} +v_{0}v_{k−1} . From Corollary 2.6, we have H_{1} ∈ U_{n}^{g}(μ) and q(H_{1}) > q(G^{∗}), a contradiction. Hence, the pendant paths of G^{∗} have length at most 2.

For each vertex u ∈ V (T − z), we prove that d(u) ⩽ 2. Otherwise, there must exist some vertex u_{0} of T −z such that d(z, u_{0}) = max{d(z, v)|v ∈ V (T), d(v) ⩾ 3}. By similar reasoning as that of above, the pendant paths attached at u_{0} have length at most 2 by Corollary 2.6. Furthermore, there exists an internal path between u_{0} and some vertex w of T, denoted by P̄ : u_{0}w_{1} …w_{m} (w_{m} = w). If m ⩾ 2, let H_{2} be the graph obtained from G^{∗} − u_{0}w_{1} − w_{1}w_{2} by amalgamating u_{0}, w_{1} and w_{2} to form a new vertex s_{1} together with attaching a new pendant path s_{1}s_{2}s_{3} of length 2 at s_{1}. From Lemma 2.2, we have H_{2} ∈ U_{n}^{g}(μ) and q(H_{2}) > q(G^{∗}), a contradiction. If m = 1, by Theorem 3.2, Lemma 2.4 and Corollary 2.5, we can get a new graph H_{3} ∈ U_{n}^{g}(μ) and q(H_{3}) > q(G^{∗}), a contradiction.

Thus, we have that the tree T is obtained by attaching some pendant paths of length at most 2 at z.

From Corollary 2.2, we have that all the pendant paths of length 2 in G^{∗} must be attached at the same vertex of C_{g}.

Now we prove that for cycle C_{g} of G^{∗}, g = 3. Assume that the cycle C_{g} of G^{∗} with length at least 4. From Lemma 2.2, we have that each internal path of G^{∗} has length 1. From Corollary 2.4, there exists at most one vertex of C_{g} such that it is attached more than one path of length 1. Then there must exist edges v_{1}v_{2} ∈ E(G^{∗}), v_{1}v_{3} ∈ E(C_{g}), v_{1}v_{4} ∈ E(C_{g}) and d(v_{1}) = 3, d(v_{2}) = 1, d(v_{3}) ⩾ 3 and d(v_{4}) ⩾ 3. Let H_{4} (H_{5}) be the graph obtained from G^{∗} − v_{1}v_{3} (G^{∗} − v_{1}v_{4}) by amalgamating v_{1} and v_{3} (v_{4}) to form a new vertex y_{1} (y_{3}) together with subdivising the edge y_{1}v_{2} (y_{3}v_{2}) with a new vertex y_{2} (y_{4}). From Theorem 3.1 and Lemma 2.4, we have either q(H_{4} − y_{2}v_{2} + y_{1}v_{2}) > q(H_{4}) > q(G^{∗}) or q(H_{5} − y_{4}v_{2} + y_{3}v_{2}) > q(H_{5}) > q(G^{∗}) and μ(H_{4} − y_{2}v_{2} + y_{1}v_{2}) ⩽ μ(G^{∗}) ⩽ μ(H_{4}), μ(H_{5} − y_{4}v_{2} + y_{3}v_{2}) ⩽ μ(G^{∗}) ⩽ μ(H_{5}), a contradiction. Hence, g = 3.

Thus, by Corollaries 2.3 and 2.4, we have G^{∗} is the graph obtained by attaching the pendant paths of length at most 2 at the same vertex of C_{3} of \overline{G}, where \overline{G} is one of the graphs C_{3}, \overline{G}_{1}, \overline{G}_{2}, and \overline{G}_{3} (see Figure 2). Then G^{∗} is isomorphic to one of graphs G_{1}, G_{2}, G_{3} and G_{4}. From Lemma 3.1, we know q(G_{1}) > q(G_{2}) and q(G_{1}) > q(G_{3}). If G^{∗} = G_{4} (in this case, n = 2μ + 1), by Lemma 2.4, we have q(G_{1}) > q(G_{4}). Thus, G^{∗} = G_{1}, and the result follows. □

References

1. R. A. Brualdi, E. S. Solheid, On the spectral radius of connected graphs, Publ. Inst. Math., Nouv. Sér. 39(53) (1986), 45–54.

2. A. Chang, F. Tian, On the spectral radius of unicyclic graphs with perfect matchings, Linear Algebra Appl. 370 (2003), 237–250.

3. A. Chang, F. Tian, A. Yu, On the index of bicyclic graphs with perfect matchings, Discr. Math. 283 (2004), 51–59.

4. L. Collatz, U. Sinogowitz, Spektren endlicher grapen, Abh. Math. Sem. Univ. Hamburg. 21 (1957), 63–77.

5. D. Cvetković, M. Doob, H. Sachs, Spectra of graphs, third ed., Johann Ambrosius Barth, Heidelberg, Leipzig, 1995.

6. D. Cvetković, P. Rowlinson, Spectra of unicyclic graphs, Graphs Combin. 3 (1987), 7–23.

7. D. Cvetković, P. Rowlinson, S. K. Simić, Signless Laplacian of finite graphs, Linear Algebra Appl. 423 (2007), 155–171.

8. D. Cvetković, S. K. Simić, Towards a spectral theory of graphs based on the signless Laplacian I, Publ. Inst. Math., Nouv. Sér. 85(99) (2009) 19–33.

9. A. Yu, F. Tian, On the spectral radius of unicyclic graphs, MATCH Commun. Math. Comput. Chem. 51 (2004), 97–109.

10. R. Grone, R. Merris, V. S. Sunder, The Laplacian spectrum of a graph, Siam J. Matrix Anal. Appl. 11 (1990), 218–238.

11. J.-M. Guo, The Laplacian spectral radius of a graph under perturbation, Computers Math. Appl. 54 (2007), 709–720.

12. , On the spectral radius of unicyclic graphs with fixed matching number, Discr. Math. 308 (2008), 6115–6131.

13. S. G. Guo, First six unicyclic graphs of order n with largest spectral radius, Appl. Math. J. Chinese Univ. Ser. A 18(4) (2003), 480–486.

14. Y. Hong, On the spectra of unicycle graph, J. East China Norm. Uni. Natur. Sci. Ed. 1 (1986), 31–34.

15. Y. Hong, X. D. Zhang, Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrices of trees, Discr. Math. 296 (2005), 187–197.

16. Q. Li, K. Q. Feng, On the largest eigenvalue of graphs, Acta Math. Appl. Sinica 2 (1979), 167–175 (in Chinese).

17. A. J. Schwenk, R. J. Wilson, On the eigenvalues of a graph; in: L. W. Beineke, R. J. Wilson (Eds.), Selected Topics in Graph Theory, Academic Press, London, 1978, 307–336 (Chapter II).

18. B. Zhou, I. Gutman, A connection between ordinary and Laplacian spectra of bipartite graphs, Linear Multilinear Algebra 56 (2008), 305–310.

School of Mathematical Sciences (Received 19 12 2012) University of Electronic Science and Technology of China (Revised 06 11 2013) Sichuan, Chengdu, 611731 China

Zhangjm7519@126.com
tingzhuhuang@126.com

College of Science China University of Petroleum Shandong, QingDao, 266580 China

Zhangjm7519@126.com

College of Science East China University of Science and Technology Shanghai, 200237 China (Corresponding author)

jimingguo@hotmail.com