# On the Signless Laplacian Spectral Radius of Bicyclic Graphs with Perfect Matchings

Authors: Jing-Ming Zhang; Ting-Zhu Huang; Ji-Ming Guo
Journal: The Scientific World Journal
 (2014)

---

## Abstract

The graph with the largest signless Laplacian spectral radius among all bicyclic graphs with perfect matchings is determined.


---

## Body

## 1. Introduction

LetG=(V,E) be a simple connected graph with vertex set V={v1,v2,…,vn} and edge set E. Its adjacency matrix A(G)=(aij) is defined as n×n matrix (aij), where aij=1 if vi is adjacent to vj, and aij=0, otherwise. Denote by d(vi) or dG(vi) the degree of the vertex vi. Let Q(G)=D(G)+A(G) be the signless Laplacian matrix of graph G, where D(G)=diag⁡(d(v1),d(v2),…,d(vn)) denotes the diagonal matrix of vertex degrees of G. It is well known that A(G) is a real symmetric matrix and Q(G) is a positive semidefinite matrix. 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 a nonnegative irreducible matrix. By the well-known Perron-Frobenius theory, ρ(G) is simple and has a unique positive unit eigenvector and so does q(G). We refer to such an eigenvector corresponding to q(G) as the Perron vector of G.Two distinct edges in a graphG are independent if they are not adjacent in G. A set of mutually independent edges of G is called a matching of G. A matching of maximum cardinality is a maximum matching in G. A matching M that satisfies 2|M|=n=|V(G)| is called a perfect matching of the graph G. Denote by Cn and Pn the cycle and the path on n vertices, respectively.The characteristic polynomial ofA(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 bicyclic graph is a connected graph in which the number of vertices equals the number of edges minus one. LetCp and Cq be two vertex-disjoint cycles. Suppose that v1 is a vertex of Cp and vl is a vertex of Cq. Joining v1 and vl by a path v1v2⋯vl of length l-1, where l≥1 and l=1 means identifying v1 with vl, denoted by B(p,l,q), is called an ∞-graph (see Figure 1). Let Pl+1,Pp+1, and Pq+1 be the three vertex-disjoint paths, where l,p,q≥1, and at most one of them is 1. Identifying the three initial vertices and the three terminal vertices of them, respectively, denoted by P(l,p,q), is called a θ-graph (see Figure 2).Figure 1
B
(
p
,
1
,
q
) and B(p,l,q)(l≥2).Figure 2
P
(
p
,
l
,
q
).LetBn(2μ) be the set of all bicyclic graphs on n=2μ(μ≥2) vertices with perfect matchings. Obviously Bn(2μ) consists of two types of graphs: one type, denoted by Bn+(2μ), is a set of graphs each of which is an ∞-graph with trees attached; the other type, denoted by Bn++(2μ), is a set of graphs each of which is θ- graph with trees attached. Then we have Bn(2μ)=Bn+(2μ)∪Bn++(2μ).The investigation on the spectral radius of graphs is an important topic in the theory of graph spectra, in which some early results can go back to the very beginnings (see [1]). 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 and Tian gave the first two spectral radii of unicyclic graphs with perfect matchings. Recently, Yu and Tian [3] gave the first two spectral radii of unicyclic graphs with a given matching number; Guo [4] gave the first six spectral radii over the class of unicyclic graphs on a given number of vertices; and Guo [5] 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 [6–9] and the references therein.In this paper, we deal with the extremal signless Laplacian spectral radius problems for the bicyclic graphs with perfect matchings. The graph with the largest signless Laplacian spectral radius among all bicyclic graphs with perfect matchings is determined.


## 2. Lemmas

LetG-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 1. A path P:vv1v2⋯vk in G is called a pendant path if d(v1)=d(v2)=⋯=d(vk-1)=2 and d(vk)=1. If k=1, then we say vv1 is a pendant edge of the graph G.In order to complete the proof of our main result, we need the following lemmas.Lemma 1 (see [10, 11]).
LetG be a connected graph and u,v two vertices of G. Suppose that v1,v2,…,vs∈N(v)∖{N(u)∪u}(1≤s≤d(v)) and x=(x1,x2,…,xn) is the Perron vector of G, where xi corresponds to the vertex vi(1≤i≤n). Let G* be the graph obtained from G by deleting the edges vvi and adding the edges uvi(1≤i≤s). If xu≥xv, then q(G)<q(G*).The cardinality of a maximum matching ofG is commonly known as its matching number, denoted by μ(G).From Lemma1, we have the following results.Corollary 2.
Letw and v be two vertices in a connected graph G and suppose that s paths {ww1w1′,ww2w2′,…,wwsws′} of length 2 are attached to G at w and t paths {vv1v1′,vv2v2′,…,vvtvt′} of length 2 are attached to G at v to form Gs,t. Then either q(Gs+i,t-i)>q(Gs,t)(1≤i≤t) or q(Gs-i,t+i)>q(Gs,t)(1≤i≤s)or μ(G0,s+t)=μ(Gs+t,0)=μ(Gs,t).Corollary 3.
Supposeu 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 {vv1v1′,…,vvtvt′} of length 2 are attached to G:uv at v to form L0,t. Let
(1)M1,t=L0,t-vv1-⋯-vvt+uv1+⋯+uvt.
If L0,t has a perfect matching, then we have that M1,t has a perfect matching and
(2)q(M1,t)>q(L0,t),(t≥1).An internal path of a graphG is a sequence of vertices v1,v2,…,vm with m≥2 such that(1)
the vertices in the sequences are distinct (except possiblyv1=vm);(2)
vi is adjacent to vi+1,(i=1,2,…,m-1);(3)
the vertex degreesd(vi) satisfy d(v1)≥3, d(v2)=⋯=d(vm-1)=2 (unless m=2) and d(vm)≥3.LetG be a connected graph, and uv∈E(G). The graph Guv is obtained from G by subdividing the edge uv, that is, adding a new vertex w and edges uw,wv in G-uv. By similar reasoning as that of Theorem 3.1 of [12], we have the following result.Lemma 4.
LetP:v1v2⋯vk(k≥2) be an internal path of a connected graph G. Let G′ be a graph obtained from G by subdividing some edge of P. Then we have q(G′)<q(G).Corollary 5.
Suppose thatv1v2⋯vk(k≥3) is an internal path of the graph G and v1vk∉E(G) for k=3. Let G* be the graph obtained from G-vivi+1-vi+1vi+2(1≤i≤k-2) by amalgamating vi, vi+1, and vi+2 to form a new vertex w1 together with attaching a new pendant path w1w2w3 of length 2 at w1. Then q(G*)>q(G) and μ(G*)≥μ(G).Proof.
From Lemma4 and the well-known Perron-Frobenius theorem, It is easy to prove that q(G*)>q(G). Next, we prove that μ(G*)≥μ(G). Let M be a maximum matching of G. If vivi+1∈M or vi+1vi+2∈M, then {M-{vivi+1}}∪{w2w3} or {M-{vi+1vi+2}}∪{w2w3} is a matching of G*. Thus, μ(G*)≥μ(G); If vivi+1∉M and vi+1vi+2∉M, then there exist two edges viu and vi+2v∈M. Thus, {M-{viu}}∪{w2w3} is a matching of G*. Hence, μ(G*)≥μ(G), completing the proof.LetS(G) be the subdivision graph of G obtained by subdividing every edge of G.Lemma 6 (see [13, 14]).
LetG be a graph on n vertices and m edges, Φ(G)=det⁡(xI-A(G)), Ψ(G)=det⁡(xI-Q(G)). Then Φ(S(G))=xm-nΨ(G,x2).Lemma 7 (see [15]).
Letu be a vertex of a connected graph G. Let Gk,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(Gk,l)>q(Gk+1,l-1).Corollary 8.
Suppose thatv1v2⋯vk(k≥3) is a pendant path of the graph G with d(v1)≥3. Let G* be the graph obtained from G-v1v2-v2v3 by amalgamating v1, v2, and v3 to form a new vertex w1 together with attaching a new pendant path w1w2w3of length2 at w1. Then q(G*)>q(G) and μ(G*)≥μ(G).Proof.
By Lemma7 we have q(G*)>q(G). By the proof as that of Corollary 5, we have μ(G*)≥μ(G).Lemma 9 (see [16]).
Lete=uv be an edge of G, and let C(e) be the set of all circuits containing e. Then Φ(G) satisfies
(3)Φ(G)=Φ(G-e)-Φ(G-u-v)-2∑Z‍Φ(G-V(Z)),
where the summation extends over all Z∈C(e).Lemma 10 (see [16]).
Letv be a vertex of G, and let φ(v) be the collection of circuits containing v, and let V(Z) denote the set of vertices in the circuit Z. Then the characteristic polynomial Φ(G) satisfies
(4)Φ(G)=xΦ(G-v)-∑w‍Φ(G-v-w)-2∑Z∈φ(v)‍Φ(G-V(Z)),
where the first summation extends over those vertices w adjacent to v, and the second summation extends over all Z∈φ(v).Lemma 11 (see [17]).
LetG be a connected graph, and let G′ be a proper spanning subgraph of G. Then ρ(G)>ρ(G′), and, for x≥ρ(G),Φ(G′)>Φ(G).LetΔ(G) denote the maximum degree of G. From Lemma 11, we have ρ(G)≥Δ(G).Lemma 12 (see [13]).
LetG be a connected graph, and let G′ be a proper spanning subgraph of G. Then q(G)>q(G′).Lemma 13 (see [18]).
LetG=(V,E) be a connected graph with vertex set V={v1,v2,…,vn}. Suppose that v1v2∈E(G), v1v3∈E(G), v1v4∈E(G), d(v3)≥2, d(v4)≥2, d(v1)=3, and d(v2)=1. Let Gv1v3(Gv1v4) be the graph obtained from G-v1v3(G-v1v4) by amalgamating v1 and v3(v4) to form a new vertex w1(w3) together with subdivising the edge w1v2(w3v2)with a new vertexw2(w4). If q=q(G)>3+5≈5.23606, then(1)
eitherq(Gv1v3)>q(G)orq(Gv1v4)>q(G);(2)
μ(Gv1v3)≥μ(G)andμ(Gv1v4)≥μ(G).Lemma 14 (see [18]).
Supposeu is a vertex of the bicyclic graph G with dG(u)≥2. Let G:uv be a graph obtained by attaching a pendant edge uv to G at u. Suppose that a pendant edge vw1 and t paths {vv1v1′,…,vvtvt′} of length 2 are attached to G:uv at v to form L1,t. Let M0,t+1=L1,t-vv1-⋯-vvt+uv1+⋯+uvt. Then we have(1)
q(M0,t+1)>q(L1,t), (t≥1);(2)
μ(L1,t)≤μ(M0,t+1).


## 3. Main Results

Lemma 15.
LetG1,G2,…,G6 be the graphs as Figure 3. Then for μ≥3, we have q(G1)>q(Gi), (i=2,3,…,6).Figure 3
G
1
–
G
6.Proof.
From Lemma10, we have
(5)Φ(S(G1))=x(x2-1)(x4-3x2+1)μ-3(x5-4x3+3x)2-(μ-3)(x2-1)(x3-2x)×(x4-3x2+1)μ-4(x5-4x3+3x)2-x(x4-3x2+1)μ-3(x5-4x3+3x)2-4(x2-1)(x4-3x2+1)μ-3×(x5-4x3+3x)(x4-3x2+2)Φ(S(G2))=x(x2-1)(x4-3x2+1)μ-4(x5-4x3+3x)×(x9-8x7+19x5-14x3+3x)-(μ-4)(x2-1)(x3-2x)(x4-3x2+1)μ-5×(x5-4x3+3x)(x9-8x7+19x5-14x3+3x)-x(x4-3x2+1)μ-4(x5-4x3+3x)×(x9-8x7+19x5-14x3+3x)-2(x2-1)×(x4-3x2+1)μ-3×(x9-8x7+19x5-14x3+3x)-2(x2-1)(x4-3x2+1)μ-4(x5-4x3+3x)×(x8-7x6+14x4-8x2+1)-2(x2-1)×(x4-3x2+1)μ-4×(x9-8x7+19x5-14x3+3x)-2(x2-1)3(x4-3x2+1)μ-4(x5-4x3+3x).
From (5), we have
(6)Φ(S(G2))-Φ(S(G1))wwi=x3(x4-3x2+1)μ-5wwwww×[(-2+μ)x14wwwwwww+(22-10μ)x12+(-97+39μ)x10wwwwwww+(221-75μ)x8+(-278+74μ)x6wwwwwww+(189-35μ)x4+(-63+6μ)x2+8].
If μ≥12, for x≥ρ(S(G1))≥ΔS(G1)=μ+2, it is easy to prove that Φ(S(G2))-Φ(S(G1))>0. Hence, ρ(S(G1))>ρ(S(G2)) for μ≥12. When μ=4,5,…,11, by direct calculation, we also get ρ(S(G1))>ρ(S(G2)), respectively. So, ρ(S(G1))>ρ(S(G2)) for μ≥4. By Lemma 6, we know that ρ(S(G))=q(G). Hence, q(G1)>q(G2)(μ≥4). By similar method, the result is as follows.Theorem 16.
IfG∈Bn(2μ)(n≥6), then q(G)≤q(G1), with equality if and only if G=G1.Proof.
LetX=(x1,x2,…,xn)T be the Perron vector of G. From Lemma 12 and by direct calculations, we have, for μ≥3, q(G1)>q(B(3,1,3))≈5.5615>3+5. So, in the following, we only consider those graphs, which have signless Laplacian spectral radius greater than q(G)>3+5.
ChooseG*∈Bn(2μ) such that q(G*) is as large as possible. Then G* consists of a subgraph H which is one of graphs B(p,1,q), B(p,l,q), and P(p,l,q) (see Figures 1 and 2).
LetT be a tree attached at some vertex, say, z, of H; |V(T)| is the number of vertices of T including the vertex z. In the following, we prove that tree T is formed by attaching at most one path of length 1 and other paths of length 2 at z.
SupposeP:v0v1⋯vk is a pendant path of G* and vk is a pendant vertex. If k≥3, let H1=G*-v2v3+v0v3. From Corollary 8, we have H1∈Bn(2μ) and q(H1)>q(G*), which is a contradiction.
For each vertexu∈V(T-z), we prove that d(u)≤2. Otherwise, there must exist some vertex u0 of T-z such that d(z,u0)=max⁡{d(z,v)∣v∈V(T)-z,d(v)≥3}. From the above proof, we have the pendant paths attached u0 which have length of at most 2. Obviously, there exists an internal path between u0 and some vertex w of G*, denoted by P¯:u0w1⋯wm(wm=w). If m≥2, let H2 be the graph obtained from G*-u0w1-w1w2 by amalgamating u0, w1, and w2 to form a new vertex s1 together with attaching a new pendant path s1s2s3 of length 2 at s1. From Corollary 5, we have H2∈Bn(2μ) and q(H2)>q(G*), which is a contradiction. If m=1, by Lemma 14 and Corollary 3, we can get a new graph H3 such that H3∈Bn(2μ) and q(H3)>q(G*), which is a contradiction.
From the proof as above, we have the treeT which is obtained by attaching some pendant paths of length 2 and at most one pendant path of length 1 at z.
From Corollary2, we have all the pendant paths of length 2 in G* which must be attached at the same vertex of H.
In the following, we prove thatG* is isomorphic to one of graphs G1,G2,…,G6 (see Figure 3). We distinguish the following two cases:
Case  1 (
G
*
∈
B
n
+
(
2
μ
)
). We prove that G* is isomorphic to one of graphs G1, G2, and G3.
Assume that there exists some cycleCp of G* with length of at least 4. From Corollary 5, we have each internal path of G*, which is not a triangle, has length 1. Note that all the pendant paths of length 2 in G* must be attached at the same vertex, then there must exist edges v1v2∈E(G*), v1v3∈E(Cp), and v1v4∈E(Cp) and d(v1)=3, d(v2)=1, d(v3)≥3, and d(v4)≥3. Let H4(H5) be the graph obtained from G*-v1v3(G*-v1v4) by amalgamating v1 and v3(v4) to form a new vertex y1(y3) together with subdividing the edge y1v2(y3v2) with a new vertex y2(y4). From Lemma 13, we have Hi∈Bn+(2μ)(i=4,5) and either q(H4)>q(G*) or q(H5)>q(G*), which is a contradiction. Then for each cycle Cg of G*, we have g=3.
Assume thatl≥4. If there exists an internal path P¯*:vivi+1⋯vm(1≤i<m≤l) with length greater than 1 in G*. Then, by Corollary 5, we can get a new graph H6 such that q(H6)>q(G*) and H6∈Bn+(2μ), which is a contradiction. Thus, d(vi)≥3(i=1,2,…,l) and either d(v2)=3 or d(v3)=3. By Lemma 13, we can also get a new graph H7 such that q(H7)>q(G*) and H7∈Bn+(2μ), which is a contradiction. Hence, l≤3.
We distinguish the following three subcases:
Subcase  1.1 (
l
=
1
). Then G* is the graph obtained by attaching all the pendant paths of length 2 at the same vertex of G¯, where G¯ is one of graphs G¯1,…,G¯5 (see Figure 4).
Assume thatG¯=G¯2. If xu≥xv, let H8=G*-rv-sv+ru+su; if xv≥xu, let H9=G*-ut+tv. Obviously, Hi∈Bn+(2μ)(i=8,9) and either q(H8)>q(G*) or q(H9)>q(G*) by Lemma 1, which is a contradiction. By similar reasoning, we have also G¯≠G¯3.
Subcase  1.2 (
l
=
2
). Then G* is the graph obtained by attaching all the pendant paths of length 2 at the same vertex of G¯, where G¯ is one of graphs G¯6,…,G¯14 (see Figure 4).
Assume thatG¯=G¯6. If xv1≥xv2, let H10=G*-v2u+v1u; if xv2≥xv1, let H11=G*-v1r+v2r. Obviously, Hi∈Bn+(2μ)(i=10,11) and either q(H10)>q(G*) or q(H11)>q(G*) by Lemma 1, which is a contradiction. By similar reasoning, we have also G¯≠G¯j(j=6,…,14).
Subcase  1.3 (
l
=
3
). Then G* is the graph obtained by attaching all the pendant paths of length 2 at the same vertex of G¯, where G¯ is one of graphs G¯15,…,G¯20 (see Figure 4).
Assume thatG¯=G¯15. If xv1≥xv2, let H12=G*-v2v3+v1v3; if xv2≥xv1, let H13=G*-v1z1+v2z1. Obviously, Hi∈Bn+(2μ)(i=12,13) and either q(H12)>q(G*) or q(H13)>q(G*) by Lemma 1, a contradiction. By similar reasoning, we have also G¯≠G¯j(j=15,…,20).
Thus,G¯ is isomorphic to one of the graphs G¯1, G¯4 and G¯5. In the following, we prove that G* is isomorphic to one of graphs G1, G2 and G3.
Assume thatG* is obtained by attaching all the pendant paths of length 2 at vertex y4 of G¯1. If xv1≥xy4, let H14 be the graph obtained from G¯1 by attaching μ-3 pendant paths of length 2 at v1. If xy4≥xv1, let H15=G*-v1y3-v1y1-v1y2+y4y3+y4y1+y4y2. Obviously, H14=H15=G1 and q(G1)>q(G*) by Lemma 1, a contradiction. Then G*=G1. By similar reasoning, the result follows.
Case  2 (
G
*
∈
B
n
+
+
(
2
μ
)
). By similar reasoning as that of Case  1, we have G* is the graph obtained by attaching all the pendant paths of length 2 at the same vertex of G¯, where G¯ is one of graphs G¯21,…,G¯24 (see Figure 4).
From Lemma1, it is easy to prove that G¯≠G¯22 and all the pendant paths of length 2 are attached at the vertex of degree 3 of G¯21 or of degree 4 of G¯i(i=23,24). Thus, G* is isomorphic to one of graphs G4, G5 and G6 (see Figure 3).
So,G* is isomorphic to one of graphs G1,…,G6. From Lemma 15, we know q(G1)>q(Gi),(i=2,3,…,6). Thus, G*=G1.Figure 4
G
¯
1
–
G
¯
24.



---

*Source: 374501-2014-06-11.xml*