PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 92(106) (2012), 117–125 DOI: 10.2298/PIM1206117G

ORDERING CACTI WITH n VERTICES AND k CYCLES BY THEIR LAPLACIAN SPECTRAL RADII

Shu-Guang Guo and Yan-Feng Wang

Communicated by Slobodan Simić

Abstract. A graph is a cactus if any two of its cycles have at most one common vertex. In this paper, we determine the first sixteen largest Laplacian spectral radii together with the corresponding graphs among all connected cacti with n vertices and k cycles, where n ⩾ 2k + 8.

1. Introduction

Let G = (V, E) be a simple connected graph with vertex set V = {v_{1}, v_{2}, …, v_{n}} and edge set E. Denote by d(v_{i}) the degree of the vertex v_{i} of G. Let A(G) be the adjacency matrix and L(G) = D(G) − A(G) the Laplacian matrix of the graph G, where D(G) = diag(d(v_{1}), d(v_{2}), …, d(v_{n})) denotes the diagonal matrix of vertex degrees of G. It is easy to see that L(G) is a singular, semi-positive, symmetric matrix and its rows sum to 0. Denote its eigenvalues by

μ_{1}(G) ⩾ μ_{2}(G) ⩾ ⋯⩾ μ_{n}(G) = 0,

which are always enumerated in non-increasing order. We denote the largest eigenvalue μ_{1}(G) of L(G) by μ(G) and call it the Laplacian spectral radius of G. Also, let ϕ(G, λ) be the characteristic polynomial of G, i.e., ϕ(G, λ) = det(λI − L(G)).

There are a lot of relations between the Laplacian spectral radius and numerous graph invariants, and the Laplacian spectral radius of a graph has numerous applications in theoretical chemistry, combinatorial optimization, communication networks, etc. For related reference, one may see [14]. Besides, from the known fact that μ_{1}(G) + μ_{n−1} (\overline{G}) = n, we can see that the Laplacian spectral radius is of relevance to the algebraic connectivity of a graph which is a good parameter to measure how well a graph is connected. There is a good deal work on algebraic connectivity for graphs (see [1] and references therein), and particular attention has been paid to algebraic connectivity for unicyclic graphs (see [3] for example).

2010 Mathematics Subject Classification: Primary 05C50.

Supported by the National Natural Science Foundation of China (11171290), the Natural Science Foundation of Jiangsu Province (BK2010292).

Recently, the problem concerning graphs with maximal or minimal Laplacian spectral radius of a given class of graphs has been studied extensively. For related results, one may refer to [4–13] and the references therein.

A graph is a cactus, or a treelike graph, if any two of its cycles have at most one common vertex. Cacti have been studied by several authors, for example, one may see [2,15]. Let T_{n,k} denote the set of all connected cacti with n vertices and k cycles.

When k = 1, T_{n,1} is the set of all unicyclic graphs of order n. Let T_{i} (i = 1–4, 6, 8–11, 13–19) be the unicyclic graphs with n vertices shown in Fig. 2. Let T ∈ T_{n,1} and T ∉ {T_{1}, T_{2}, T_{3}, T_{4}}. Guo [7] proved that

n = μ(T_{1}) > μ(T_{2}) > μ(T_{3}) > μ(T_{4}) > μ(T).

Let T ∈ T_{n,1} and T ∉ {T_{1}, T_{2}, T_{3}, T_{4}, T_{6}, T_{8}, T_{9}, T_{10}, T_{11}, T_{17}}. Liu, Shao and Yuan [11] proved that

μ(T_{6}) > μ(T_{8}) > μ(T_{9}) > μ(T_{10}) > μ(T_{11}) = μ(T_{17}) > μ(T).

Let T ∈ T_{n,1} and T ∉ {T_{1}, T_{2}, T_{3}, T_{4}, T_{6}, T_{8}, T_{9}, T_{10}, T_{11}, T_{17}, T_{13}–T_{16}, T_{18}, T_{19}}. Liu and Liu [12] proved that

μ(T_{13}) > μ(T_{14}) = μ(T_{18}) = μ(T_{19}) > μ(T_{15}) > μ(T_{16}) > μ(T).

In this paper, we consider the cases when k ⩾ 2, and determine the first sixteen largest Laplacian spectral radii together with the corresponding graphs in T_{n,k} .

2. Preliminaries

For v ∈ V (G), N(v) denotes the set of all neighbors of vertex v in G. Then d(v) = |N(v)|. Δ denotes the maximum degree of G and δ denotes the minimum degree of G. Let G_{1}, G_{2}, …, G_{20} be the cacti with n vertices and k cycles shown in Fig. 1.

Lemma 2.1 (13). We have μ(G) ⩽ max{d(v) + m(v) : v ∈ V }, where m(v) =

∑ _{u∈N(v)} d(u)/d(v).

Lemma 2.2. Suppose k ⩾ 1 and G ∈ T_{n,k} with Δ ⩽ n − 4. If n ⩾ 2k + 8, then

μ(G) ⩽ n − 2.

Proof. By Lemma 2.1, we only need to prove that max{d(v) + m(v) : v ∈ V (G)} ⩽ n − 2. Suppose max{d(v) + m(v) : v ∈ V (G)} occurs at the vertex u. We consider the following three cases.

Case 1. d(u) = 1. Suppose v ∈ N(u), then

d(u) + m(u) = d(u) + d(v) ⩽ 1 + n − 4 < n − 2.

Case 2. d(u) = 2. Suppose v, w ∈ N(u). Note that G is a cactus, then |N(v) ∩ N(w)| ⩽ 2 and |N(v) ∪ N(w)| ⩽ n. Therefore

d(u) + m(u) = 2 + \frac{d(v) + d(w)}{2} ⩽ 2 + \frac{n + 2}{2} ⩽ n − 2.

ORDERING CACTI WITH n VERTICES AND k CYCLES 119

Case 3. 3 ⩽ d(u) ⩽ n − 4. Note that 3 ⩽ d(u) ⩽ n − 4, then

d(u) + m(u) ⩽ d(u) + \frac{2m − d(u) − 3}{d(u)} = d(u) − 1 + \frac{2m − 3}{d(u)} .

Next we shall prove that d(u)−1+ \frac{2m−3}{d(u)} ⩽ n−2. Equivalently, d(u)(n−1−d(u)) ⩾ 2m − 3. Once this is proved, we are done. Let f(x) = (n − 1 − x)x.

When x ∈ [3, \frac{n−1}{2} ], since f′(x) = n − 1 − 2x ⩾ 0, then

f(x) ⩾ f(3) = 3(n − 4) ⩾ 2(n + k − 1) − 3 = 2m − 3.

When x ∈ [\frac{n−1}{2} , n − 4], since f′(x) = n − 1 − 2x ⩽ 0, then

f(x) ⩾ f(n − 4) = 3(n − 4) ⩾ 2(n + k − 1) − 3 = 2m − 3.  □

By combing the above discussion, the conclusion follows.

Lemma 2.3 (4). Let v be a vertex in a connected graph G and suppose that s (s ⩾ 2) new paths (with equal length k) P_{i} : vv_{ik} v_{i(k−1)} …v_{i1}, (i = 1, 2, …, s; k ⩾ 1) are attached to G at v, respectively, to form a new graph G_{s}^{k}, where v_{ik} , v_{i(k−1)} , …, v_{i1}, (i = 1, 2, …, s) are distinct new vertices. Let G_{s;t_{1} ,t_{2} ,...,t_{k}}^{k} be the graph obtained from G_{s}^{k} by adding t_{i} (0 ⩽ t_{i} ⩽ \frac{s(s−1)}{2} ) edges among vertices v_{1i}, v_{2i}, …, v_{si} (1 ⩽ i ⩽ k), respectively. If Δ(G_{s}^{k}) ⩾ s + 3, then we have μ(G_{s;t_{1} ,t_{2} ,...,t_{k}}^{k} ) = μ(G_{s}^{k}).

Let T_{1}, T_{2}, …, T_{16} be the graphs with n vertices shown in Fig. 2. Then from Lemma 2.3, we can obtain easily the following lemma.

Lemma 2.4. μ(G_{1}) = μ(T_{1}), μ(G_{2}) = μ(T_{2}), μ(G_{3}) = μ(T_{3}), μ(G_{4}) = μ(T_{4}),

μ(G_{5}) = μ(T_{5}), μ(G_{6}) = μ(T_{6}), μ(G_{7}) = μ(T_{7}), μ(G_{8}) = μ(T_{8}), μ(G_{9}) = μ(G_{10}) = μ(T_{9}), μ(G_{11}) = μ(T_{10}), μ(G_{12}) = μ(G_{13}) = μ(T_{11}), μ(G_{14}) = μ(T_{12}), μ(G_{15}) = μ(T_{13}), μ(G_{16}) = μ(G_{17}) = μ(G_{18}) = μ(T_{14}), μ(G_{19}) = μ(T_{15}), μ(G_{20}) = μ(T_{16}).

Lemma 2.5 (6). Let G be a connected graph on n vertices with at least one edge; then μ(G) ⩾ Δ(G) + 1, where Δ(G) is the maximum degree of the graph G, with equality if and only if Δ(G) = n − 1.

Lemma 2.6. Let n ⩾ 10. Then n = μ(T_{1}) > μ(T_{2}) > μ(T_{3}) > μ(T_{4}) > μ(T_{5}) > μ(T_{6}) > μ(T_{7}) > μ(T_{8}) > μ(T_{9}) > μ(T_{10}) > μ(T_{11}) > μ(T_{12}) > μ(T_{13}) > μ(T_{14}) > μ(T_{15}) > μ(T_{16}).

Proof. From [7] we have n = μ(T_{1}) > μ(T_{2}) > μ(T_{3}) > μ(T_{4}), and μ(T_{i}) is the largest root of the equation h_{i}(λ) = 0 (i = 2, 3, 4), respectively, where

h_{2}(λ) = λ^{4} − (n + 5)λ^{3} + (6n + 4)λ^{2} − (10n − 4)λ + 4n,
h_{3}(λ) = λ^{4} − (n + 5)λ^{3} + (6n + 3)λ^{2} − (9n − 5)λ + 3n,
h_{4}(λ) = λ^{4} − (n + 5)λ^{3} + (6n + 4)λ^{2} − (10n − 6)λ + 3n.

It is not difficult to calculate recursively that

ϕ(T_{5}; λ) = λ(λ − 1)^{n−8} (λ^{3} − 6λ^{2} + 10λ − 4)h_{5}(λ),
ϕ(T_{6}; λ) = λ(λ − 1)^{n−5} h_{6}(λ),
ϕ(T_{7}; λ) = λ(λ − 1)^{n−8} h_{7}(λ),
ϕ(T_{8}; λ) = λ(λ − 2)(λ − 1)^{n−7} h_{8}(λ),
ϕ(T_{9}; λ) = λ(λ − 1)^{n−5} h_{9}(λ),
ϕ(T_{10}; λ) = λ(λ − 2)(λ − 1)^{n−6} h_{10}(λ),
ϕ(T_{11}; λ) = λ(λ − 1)^{n−5} h_{11}(λ),
ϕ(T_{12}; λ) = λ(λ − 1)^{n−8} h_{12}(λ),
ϕ(T_{13}; λ) = λ(λ − 1)^{n−7} h_{13}(λ),
ϕ(T_{14}; λ) = λ(λ − 3)(λ − 1)^{n−7} (λ^{2} − 3λ + 1)h_{14}(λ),
ϕ(T_{15}; λ) = λ(λ − 1)^{n−6} h_{15}(λ),
ϕ(T_{16}; λ) = λ(λ − 3)(λ − 1)^{n−6} h_{16}(λ),

where

h_{5}(λ) = λ^{4} − (n + 4)λ^{3} + (6n − 2)λ^{2} − (10n − 12)λ + 4n,
h_{6}(λ) = λ^{4} − (n + 5)λ^{3} + (7n − 1)λ^{2} − (13n − 19)λ + 4n,
h_{7}(λ) = λ^{7} − (n + 10)λ^{6} + (12n + 31)λ^{5} − (55n + 14)λ^{4} + (121n − 85)λ^{3}

− (132n − 128)λ^{2} + (66n − 44)λ − 12n,

h_{8}(λ) = λ^{5} − (n + 5)λ^{4} + (7n + 1)λ^{3} − (15n − 17)λ^{2} + (10n − 8)λ − 2n,
h_{9}(λ) = λ^{4} − (n + 5)λ^{3} + (7n − 3)λ^{2} − (11n − 17)λ + 3n,
h_{10}(λ) = λ^{4} − (n + 4)λ^{3} + (6n − 4)λ^{2} − (8n − 12)λ + 2n,
h_{11}(λ) = λ^{4} − (n + 5)λ^{3} + (7n − 1)λ^{2} − (13n − 21)λ + 3n,
h_{12}(λ) = λ^{7} − (n + 10)λ^{6} + (12n + 30)λ^{5} − (54n + 8)λ^{4} + (114n − 93)λ^{3}

− (117n − 126)λ^{2} + (54n − 39)λ − 9n,

h_{13}(λ) = λ^{6} − (n + 7)λ^{5} + (9n + 10)λ^{4} − (28n − 18)λ^{3} + (36n − 42)λ^{2}
− (18n − 14)λ + 3n,
h_{14}(λ) = λ^{3} − (n + 1)λ^{2} + (3n − 5)λ − n,
h_{15}(λ) = λ^{5} − (n + 6)λ^{4} + (8n + 4)λ^{3} − (20n − 22)λ^{2} + (17n − 26)λ − 3n,
h_{16}(λ) = λ^{4} − (n + 3)λ^{3} + (5n − 4)λ^{2} − (6n − 10)λ + n.

Since n ⩾ μ(T_{i}) > Δ(T_{i}) + 1 ⩾ n − 2 ⩾ 8, it follows that μ(T_{i}) is the largest root of the equation h_{i}(λ) = 0(i = 5, …, 16) respectively. Next we shall divide the proof into the next 11 steps.

(1) μ(T_{4}) > μ(T_{5}). It is easy to see that h_{4}(λ) = h_{5}(λ) − (λ^{2}(λ − 6) + 6λ + n) and h_{4}(μ(T_{5})) < 0. So we have μ(T_{4}) > μ(T_{5}).

(2) μ(T_{5}) > μ(T_{6}). Note that h_{5}(λ) = h_{6}(λ) + γ_{1}(λ), where

γ_{1}(λ) = λ(λ^{2} − (n + 1)λ + 3n − 7).

Let α_{1} denote the maximum root of γ_{1}(λ) = 0. Since γ_{1}(−1) < 0, γ_{1}(2) > 0, γ_{1}(n − 2) < 0, γ_{1}(n − 1) > 0, it is easy to see that n − 2 < α_{1} < n − 1.

Note that h_{6}(λ) = (λ−4)γ_{1}(λ)+(2λ^{2}−(n+9)λ+4n), then h_{6}(λ) > 0 for λ ⩾ α_{1}. Thus μ(T_{6}) < α_{1}. Note that lim_{λ→∞} γ_{1}(λ) = +∞, thus h_{5}(μ(T_{6})) = γ_{1}(μ(T_{6})) < 0. This implies that μ(T_{5}) > μ(T_{6}).

(3) μ(T_{6}) > μ(T_{7}). It is easy to see that h_{7}(λ) = γ_{2}(λ)h_{6}(λ) + γ_{3}(λ), where

γ_{2}(λ) = (λ − 1)^{2}(λ − 3), γ_{3}(λ) = λ(2λ^{2} − 8λ − n + 13).

Since μ(T_{7}) > n − 2 ⩾ 8, it follows that γ_{2}(μ(T_{7})) > 0 and γ_{3}(μ(T_{7})) > 0. This implies that h_{6}(μ(T_{7})) < 0. Thus μ(T_{6}) > μ(T_{7}).

(4) μ(T_{7}) > μ(T_{8}). It is easy to see that h_{7}(λ) = (λ^{2} − 5λ + 5)h_{8}(λ) − γ_{4}(λ), where

γ_{4}(λ) = λ^{4} − (n + 3)λ^{3} + (5n − 3)λ^{2} − (6n − 4)λ + 2n
= λ^{2}(λ^{2} − (n + 3)λ + 5n − 10) + (7λ^{2} − (6n − 4)λ + 2n).

It is easy to see that γ_{4}(μ(T_{8})) > 0. So we have h_{7}(μ(T_{8})) < 0, thus μ(T_{7}) > μ(T_{8}). (5) From [11] we have μ(T_{8}) > μ(T_{9}) > μ(T_{10}).

(6) μ(T_{10}) > μ(T_{11}). Note that h_{10}(λ) = h_{11}(λ) + γ_{5}(λ), where
γ_{5}(λ) = λ^{3} − (n + 3)λ^{2} + (5n − 9)λ − n.

Let α_{2} denote the maximum root of γ_{5}(λ) = 0. Since γ_{5}(−∞) < 0, γ_{5}(\frac{1}{2}) = \frac{5n}{4} − \frac{41}{8} > 0, γ_{5}(n − 2) < 0, γ_{5}(n − 1) > 0, thus n − 2 < α_{2} < n − 1.

Note that h_{11}(λ) = (λ − 2)γ_{5}(λ) + 2λ^{2} − (2n − 3)λ + n, then h_{11}(α_{2}) = 2α_{2}^{2} − (2n − 3)α_{2} + n > 0 and h_{11}(λ) > 0 for λ ⩾ α_{2}. Thus μ(T_{11}(λ)) < α_{2}. Note that lim_{λ→∞} γ_{5}(λ) = +∞, thus h_{10}(μ(T_{11})) = γ_{5}(μ(T_{11})) < 0. This implies that μ(T_{10}) > μ(T_{11}), because lim_{λ→∞} h_{10}(λ) = +∞.

(7) μ(T_{11}) > μ(T_{12}). Note that h_{12}(λ) = γ_{6}(λ)h_{11}(λ) − γ_{7}(λ), where

γ_{6}(λ) = λ^{3} − 5λ^{2} + 6λ − 4, γ_{7}(λ) = 2λ^{3} − (4n − 4)λ^{2} + (16n − 45)λ − 3n.

It is easy to see that γ_{6}(μ(T_{12})) > 0. Note that γ_{7}(−∞) < 0, γ_{7}(1) > 0, γ_{7}(n − 1) < 0 , γ_{7}(n − 2) < 0, γ_{7}(+∞) > 0 and n − 2 < μ(T_{12}) < n − 1. It follows that γ_{7}(μ(T_{12})) < 0. So we have h_{11}(μ(T_{12})) < 0, thus μ(T_{11}) > μ(T_{12}).

(8) μ(T_{12}) > μ(T_{13}). Note that h_{12}(λ) = (λ − 3)h_{13}(λ) − γ_{8}(λ), where

γ_{8}(λ) = λ^{5} − (n + 4)λ^{4} + (6n − 3)λ^{3} − (9n − 14)λ^{2} + (3n − 3)λ.

We also have h_{12}(λ) = (λ − 3)^{2}γ_{8}(λ) − γ_{9}(λ), where

γ_{9}(λ) = 4λ^{4} − (3n + 21)λ^{3} + (18n + 18)λ^{2} − (27n − 12)λ + 9n
= 3λ^{4} − (3n − 6)λ^{3} + λ^{2}(λ^{2} − 27λ + 18n − 15) + 33λ^{2} − (27n − 12)λ + 9n.

It is easy to see that γ_{9}(λ) > 0 for λ ⩾ μ(T_{12}). So we have γ_{8}(λ) > 0 for λ ⩾ μ(T_{12}). Thus h_{13}(λ) > 0 for λ ⩾ μ(T_{12}). It follows that μ(T_{12}) > μ(T_{13}).

(9) μ(T_{13}) > μ(T_{14}). Note that h_{13}(λ) = (λ^{3} − 6λ^{2} + 9λ − 3)h_{14}(λ) − λ. It is easy to see that h_{13}(μ(T_{14})) < 0. Thus μ(T_{13}) > μ(T_{14}).

(10) μ(T_{14}) > μ(T_{15}). Note that h_{15}(λ) = (λ^{2} − 5λ + 4)h_{14}(λ) + (λ^{2} − 6λ + n). It is easy to see that h_{14}(μ(T_{15})) < 0. Thus μ(T_{14}) > μ(T_{15}).

(11) μ(T_{15}) > μ(T_{16}). Note that h_{15}(λ) = (λ − 3)h_{16}(λ) − λ(λ^{2} − nλ + 2n − 4). It is easy to see that h_{15}(μ(T_{16})) < 0. Thus μ(T_{15}) > μ(T_{16}).

By combining the above discussion, we have μ(T_{4}) > μ(T_{5}) > μ(T_{6}) > μ(T_{7}) > μ(T_{8}) > μ(T_{9}) > μ(T_{10}) > μ(T_{11}) > μ(T_{12}) > μ(T_{13}) > μ(T_{14}) > μ(T_{15}) > μ(T_{16}). □

3. Main results

Theorem 3.1. Let G be a connected cactus with n vertices and k cycles, and G_{1}, G_{2}, …, G_{20} be the cacti with n vertices and k cycles shown in Fig. 1, where k ⩾ 2 and n ⩾ 2k + 8.

(1) If G ∉ {G_{1}, …, G_{20}}, then μ(G) ⩽ n − 2 < μ(G_{20}).

(2) n = μ(G_{1}) > μ(G_{2}) > μ(G_{3}) > μ(G_{4}) > μ(G_{5}) > μ(G_{6}) > μ(G_{7}) >

μ(G_{8}) > μ(G_{9}) = μ(G_{10}) > μ(G_{11}) > μ(G_{12}) = μ(G_{13}) > μ(G_{14}) > μ(G_{15}) > μ(G_{16}) = μ(G_{17}) = μ(G_{18}) > μ(G_{19}) > μ(G_{20}), and μ(G_{i}) is the largest root of the equation f_{i}(λ) = 0(i = 2, …, 20) respectively, where

f_{2}(λ) = λ^{4} − (n + 5)λ^{3} + (6n + 4)λ^{2} − (10n − 4)λ + 4n,
f_{3}(λ) = λ^{4} − (n + 5)λ^{3} + (6n + 3)λ^{2} − (9n − 5)λ + 3n,
f_{4}(λ) = λ^{4} − (n + 5)λ^{3} + (6n + 4)λ^{2} − (10n − 6)λ + 3n,
f_{5}(λ) = λ^{4} − (n + 4)λ^{3} + (6n − 2)λ^{2} − (10n − 12)λ + 4n,
f_{6}(λ) = λ^{4} − (n + 5)λ^{3} + (7n − 1)λ^{2} − (13n − 19)λ + 4n,
f_{7}(λ) = λ^{7} − (n + 10)λ^{6} + (12n + 31)λ^{5} − (55n + 14)λ^{4} + (121n − 85)λ^{3}
− (132n − 128)λ^{2} + (66n − 44)λ − 12n,
f_{8}(λ) = λ^{5} − (n + 5)λ^{4} + (7n + 1)λ^{3} − (15n − 17)λ^{2} + (10n − 8)λ − 2n,
f_{9}(λ) = f_{10}(λ) = λ^{4} − (n + 5)λ^{3} + (7n − 3)λ^{2} − (11n − 17)λ + 3n,

f_{11}(λ) = λ^{4} − (n + 4)λ^{3} + (6n − 4)λ^{2} − (8n − 12)λ + 2n,
f_{12}(λ) = f_{13}(λ) = λ^{4} − (n + 5)λ^{3} + (7n − 1)λ^{2} − (13n − 21)λ + 3n,
f_{14}(λ) = λ^{7} − (n + 10)λ^{6} + (12n + 30)λ^{5} − (54n + 8)λ^{4} + (114n − 93)λ^{3}
− (117n − 126)λ^{2} + (54n − 39)λ − 9n,
f_{15}(λ) = λ^{6} − (n + 7)λ^{5} + (9n + 10)λ^{4} − (28n − 18)λ^{3} + (36n − 42)λ^{2}
− (18n − 14)λ + 3n,
f_{16}(λ) = f_{17}(λ) = f_{18}(λ) = λ^{3} − (n + 1)λ^{2} + (3n − 5)λ − n,
f_{19}(λ) = λ^{5} − (n + 6)λ^{4} + (8n + 4)λ^{3} − (20n − 22)λ^{2} + (17n − 26)λ − 3n,
f_{20}(λ) = λ^{4} − (n + 3)λ^{3} + (5n − 4)λ^{2} − (6n − 10)λ + n.

Proof. It is easy to check that G_{1}, G_{2}, …, G_{20} are all the cacti with n vertices, k cycles and maximum degree greater than n − 4. Then Δ(G) ⩽ n − 4 for G ∉ {G_{1}, …, G_{20}}. By Lemma 2.2, we have μ(G) ⩽ n − 2. By Lemmas 2.4 and 2.6, μ(G_{20}) = μ(T_{16}) is the largest root of the equation

f_{20}(λ) = h_{16}(λ) = λ^{4} − (n + 3)λ^{3} + (5n − 4)λ^{2} − (6n − 10)λ + n = 0.

Since h_{16}(n − 2) = −n + 4 < 0, it follows that μ(G_{20}) > n − 2. Thus

μ(G) ⩽ n − 2 < μ(G_{20}).

This completes the proof of (1).

The proof of (2) follows from Lemma 2.4, Lemma 2.6 and the proof of Lemma 2.6 immediately. □

References

1. N. M. M. Abreu, Old and new results on algebraic connectivity of graphs, Linear Algebra Appl. 423(1) (2007), 53–73.

2. B. Borovićanin, M. Petrović, On the index of cactuses with n vertices, Publ. Inst. Math. (Beograd) 79(93) (2006), 13-18.

3. S. Fallat, S. Kirkland, S. Pati, Maximizing algebraic connectivity over unicyclic graphs, Linear Multilinear Algebra 51(3) (2003), 221–241.

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

5. J. M. Guo, On the Laplacian spectral radius of a tree, Linear Algebra Appl. 368 (2003), 379– 385.

6. R. Grone, R. Merris, The Laplacian spectrum of graph II, SIAM J. Discrete Math. 7 (1994), 221–229.

7. S. G. Guo, The largest eigenvalues of the Laplacian matrices of unicyclic graphs, Appl. Math. J. Chinese Univ. Ser. A 16(2) (2001), 131–135. (in Chinese)

8. S. G. Guo, Ordering trees with n vertices and diameter d by their largest Laplacian eigenvalues, Util. Math. 74 (2007), 65–69.

9. S. G. Guo, Ordering trees with n vertices and matching number q by their largest Laplacian eigenvalues, Discrete Math. 308 (2008), 4608–4615.

10. C. X. He, J. Y. Shao, J. L. He, On the Lapalcian spectral radii of bicyclic graphs, Discrete Math. 308(24) (2008), 5981–5995.

11. Y. Liu, J. Y. Shao, X. Y. Yuan, Some results on the ordering of the Laplacian spectral radii of unicyclic graphs, Discrete Appl. Math. 156(14) (2008), 2679–2697.

12. Y. Liu, Y. Liu, Ordering of unicyclic graphs with Laplacian spectral radii, J. Tongji Univ. 36 (2008), 841–843. (in Chinese)

13. R. Merris, A note on Laplacian graph eigenvalues, Linear Algebra Appl. 285 (1998), 33–35.

14. B. Mohar, Some applications of Laplace eigenvalues of graphs. Notes taken by Martin Juvan, (English), in: G. Hahn et al. (Eds.) Graph Symmetry: Algebraic Methods and Applications, NATO ASI Ser., Ser.C, Math. Phys. Sci., vol. 497, Kluwer, Dordrecht, 1997, 225–275.

15. Z. Radosavljević, M. Ras̆ajski, A class of reflexive cactuses with four cycles, Univ. Beograd Publ. Elektrotehn. Fak., Ser. Mat. 14 (2003), 64–85.

School of Mathematical Sciences (Received 20 04 2010) Yancheng Teachers University (Revised 18 05 2011) Yancheng 224002, Jiangsu P. R. China

ychgsg@yahoo.com.cn