Bulletin T.CXXXI de l’Académie serbe des sciences et des arts − 2005 Classe des Sciences mathématiques et naturelles Sciences mathématiques, N\underline{o} 30

ON THE SPECTRAL RADIUS OF BICYCLIC GRAPHS

M. PETROVIĆ, I. GUTMAN, SHU-GUANG GUO

(Presented at the 3rd Meeting, held on April 22, 2005)

A b s t r a c t. Let K_{3} and K′_{3} be two complete graphs of order 3 with disjoint vertex sets. Let B_{n}^{∗}(0) be the 5-vertex graph, obtained by identifying a vertex of K_{3} with a vertex of K′_{3} . Let B_{n}^{∗∗}(0) be the 4-vertex graph, obtained by identifying two vertices of K_{3} each with a vertex of K′_{3} . Let B_{n}^{∗}(k) be graph of order n, obtained by attaching k paths of almost equal length to the vertex of degree 4 of B_{n}^{∗}(0) . Let B_{n}^{∗∗}(k) be the graph of order n, obtained by attaching k paths of almost equal length to a vertex of degree 3 of B_{n}^{∗∗}(0) . Let B_{n}(k) be the set of all connected bicyclic graphs of order n, possessing k pendent vertices. One of the authors recently proved that among the elements of B_{n}(k) , either B_{n}^{∗}(k) or B_{n}^{∗∗}(k) have the greatest spectral radius. We now show that for k ≥ 1 and n ≥ k + 5 , among the elements of B_{n}(k) , the graph B_{n}^{∗}(k) has the greatest spectral radius.

AMS Mathematics Subject Classification (2000): 05C50, 05C35 Key Words: spectrum (of graph), spectral radius (of graph), bicyclic

graphs, extremal graphs

1. Introduction

The spectral radius (the greatest graph eigenvalue, also called “index”) is an important and much studied spectral property of graphs [1–3]. In a recent work [4] one of the present authors examined the spectral radius of connected bicyclic graphs of order n, possessing k pendent vertices (vertices of degree 1), and arrived at the following result.

Let K_{3} and K′_{3} be two complete graphs of order 3 with disjoint vertex sets. Let B_{n}^{∗}(0) be the 5-vertex graph, obtained by identifying a vertex of K_{3} with a vertex of K′_{3} . Let B_{n}^{∗∗}(0) be the 4-vertex graph, obtained by identifying two vertices of K_{3} each with a vertex of K′_{3} . In other words, B_{n}^{∗∗}(0) is the graph obtained by deleting an edge from K_{4} .

By P_{ℓ} is denoted the path of order ℓ. Two paths P_{ℓ} and P_{ℓ′} are said to be of almost equal length, if |ℓ − ℓ′| ≤ 1 .

The set of all connected bicyclic graphs of order n, possessing k pendent vertices will be denoted by B_{n}(k) .

The graph B_{n}^{∗}(k) ∈ B_{n}(k) is obtained by attaching k paths of almost equal length to the vertex of degree 4 of B_{n}^{∗}(0) . The graph B_{n}^{∗∗}(k) ∈ B_{n}(k) is obtained by attaching k paths of almost equal length to the vertex of degree 3 of B_{n}^{∗∗}(0) .

Note that both B_{n}^{∗}(k) and B_{n}^{∗∗}(k) exist if and only if k ≥ 1 and n ≥ k+5 .

Theorem 1 [4]. Provided that both B_{n}^{∗}(k) and B_{n}^{∗∗}(k) exist, among the elements of B_{n}(k) , either B_{n}^{∗}(k) or B_{n}^{∗∗}(k) have the greatest spectral radius.

The obvious question that emerges from Theorem 1 is which of the two graphs B_{n}^{∗}(k) , B_{n}^{∗∗}(k) has greater spectral radius. Solving this seemingly simple problem it turned out to be not quite easy. In this paper we offer its solution:

Theorem 2. Provided that both B_{n}^{∗}(k) and B_{n}^{∗∗}(k) exist, the spectral radius of B_{n}^{∗}(k) is greater than the spctral radius of B_{n}^{∗∗}(k) .

In order to prove Theorem 2 we need some preparations.

2. Some Auxiliary Results

Let G be a simple graph (i.e., a graph without loops, multiple and/or directed and/or weighted edges). Its vertex and edge sets of a graph G are denoted by V (G) and E(G) , respectively. The graph G has n vertices, i.e., |V (G)| = n.

The eigenvalues of G will be denoted by λ_{i} = λ_{i}(G) and, as usual [1], it is assumed that λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n}. If the graph G is connected, then λ_{1} > λ_{2} .

The characteristic polynomial of the graph G is denoted by ϕ(G, λ) . We need the following well known Lemmas [1].

Lemma 1. Let v be a vertex of G and let C(v) be the set of all cycles of G that contain v. Then

ϕ(G, λ) = λ ϕ(G−v, λ)− ∑_{(u,v)∈E(G)} ϕ(G−u−v, λ)−2 ∑_{Z∈C(v)} ϕ(G−V (Z), λ),

where G − V (Z) is the graph obtained by removing from G the vertices belonging to Z.

Lemma 2. Let v be a vertex of G, let λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n} be the eigenvalues of the graph G, and let μ_{1} ≥ μ_{2} ≥ ⋯ ≥ μ_{n−1} be the eigenvalues of G − v. Then the inequalities

λ_{1} ≥ μ_{1} ≥ λ_{2} ≥ μ_{2} ≥ ⋯ ≥ μ_{n−1} ≥ λ_{n}

hold. If G is connected, then λ_{1} > μ_{1} .

Lemma 3. The characteristic polynomial of the n-vertex path P_{n} satisfies the expression

ϕ(P_{n}, λ) = \frac{1}{\sqrt{λ^{2} − 4}} (x_{1}^{n+1} − x_{2}^{n+1}) ,

where

x_{1} = \frac{1}{2} (λ + \sqrt{λ^{2} − 4}) and x_{2} = \frac{1}{2} (λ − \sqrt{λ^{2} − 4})

are the roots of the equation x^{2} − λ x + 1 = 0 .

Lemma 4. If the graphs G and H have exactly one eigenvalue greater than some constant a, and if ϕ(G, λ_{1}(H)) > 0 , then λ_{1}(G) < λ_{1}(H) .

In the proof that follows the special case of Lemma 4, for a = 2 will be used.

3. Proof of Theorem 2

The graphs B_{n}^{∗}(k) and B_{n}^{∗∗}(k) are defined above. Evidently, in the case of B_{n}^{∗}(k) it must be k ≤ n − 5 whereas in the case of B_{n}^{∗∗}(k) it must be k ≤ n − 4 . If k = n − 4 then B_{n}^{∗}(k) does not exist, and then among the elements of B_{n}(k) the graph B_{n}^{∗∗}(k) has the greatest spectral radius. Therefore in the following we assume that k < n − 4 . If so, then at least one path attached to B_{n}^{∗∗}(k) possesses at least two vertices (ℓ ≥ 2).

The vertex of B_{n}^{∗}(k) that has degree k + 4 is denoted by v. Also the vertex of B_{n}^{∗∗}(k) that has degree k + 3 is denoted by v. Denote by ℓ the maximal number of vertices of a path attached to the vertex v of B_{n}^{∗∗}(k) . As already explained, ℓ ≥ 2 .

Let B^{∗∗} be the graph analogous to B_{n}^{∗∗}(k) in which all paths attached to vertex v have ℓ vertices.

Let B^{∗} be the graph analogous to B_{n}^{∗}(k) in which all paths attached to vertex v have ℓ − 1 vertices.

Evidently, B^{∗} is an induced subgraph of B_{n}^{∗}(k) whereas B_{n}^{∗∗}(k) is an induced subgraph of B^{∗∗}. Therefore, by Lemma 2,

λ_{1}(B^{∗}) ≤ λ_{1}(B_{n}^{∗}(k))

with equality if and only if n = (ℓ − 1)k + 5 . Also,

λ_{1}(B^{∗∗}) ≥ λ_{1}(B_{n}^{∗∗}(k))

with equality if and only if n = ℓ k + 4 .

Thus for the proof of the Theorem it is sufficient to show that λ_{1}(B^{∗∗}) < λ_{1}(B^{∗}) . We do this in the following.

Because of Lemma 2, the graphs B^{∗∗} and B^{∗} have exactly one eigenvalue greater than 2. (This is because all components of the subgraphs B^{∗∗}−v and B^{∗} − v are paths, and the spectral radii of paths are less than 2. Therefore λ_{2}(B^{∗∗}) < 2 and λ_{2}(B^{∗}) < 2 . By direct calculation we check that in the case n = 6 , k = 1 , the greatest eigenvalues of B^{∗∗} and B^{∗} are greater than 2. Therefore the greatest eigenvalues of B^{∗∗} and B^{∗} are greater than 2 for all values of n and k.)

Consequently, Lemma 4 is applicable to B^{∗∗} and B^{∗} and it is sufficient to show that ϕ(B^{∗∗}, λ_{1}(B^{∗})) > 0 .

By applying Lemma 1 to the vertex v of B^{∗∗} we obtain

ϕ(B^{∗∗}, λ) = λ ϕ(P_{ℓ}, λ)^{k−1} [(λ^{3} − 5 λ − 4) ϕ(P_{ℓ}, λ) − k (λ^{2} − 2) ϕ(P_{ℓ−1}, λ)] .

In an analogous manner we obtain

ϕ(B^{∗},λ) = (λ^{2}−1) ϕ(P_{ℓ−1}, λ)^{k−1} [(λ^{3}−5λ−4) ϕ(P_{ℓ−1}, λ)−k (λ^{2}−1) ϕ(P_{ℓ−2}, λ)] .

Denote the greatest eigenvalue of B^{∗} by r. For n = 6 and k = 1 the greatest eigenvalue of B^{∗} is 2.709…. Therefore, for any n and k,

r = λ_{1}(B^{∗}) ≥ 2.709 .

From the above expression for ϕ(B^{∗}, λ) it is seen that r satisfies the equation

(r^{3} − 5 r − 4) ϕ(P_{ℓ−1}, r) − k (r^{2} − 1) ϕ(P_{ℓ−2}, r) = 0

from which

k = \frac{(r^{3} − 5 r − 4) ϕ(P_{ℓ−1}, r)}{(r^{2} − 1) ϕ(P_{ℓ−2}, r)} .

Now, the inequality ϕ(B^{∗∗}, r) > 0 holds if and only if

r ϕ(P_{ℓ}, r)^{k−1} [(r^{3} − 5 r − 4) ϕ(P_{ℓ}, r) − k (r^{2} − 2) ϕ(P_{ℓ−1}, r)] > 0

if and only if

(r^{3} − 5 r − 4) ϕ(P_{ℓ}, r) − k (r^{2} − 2) ϕ(P_{ℓ−1}, r) > 0

if and only if

(r^{3} − 5 r − 4) ϕ(P_{ℓ}, r) − \frac{(r^{3} − 5 r − 4) ϕ(P_{ℓ−1}, r)}{(r^{2} − 1) ϕ(P_{ℓ−2}, r)} (r^{2} − 2) ϕ(P_{ℓ−1}, r) > 0 .

Now, the expression r^{3} − 5 r − 4 is positive–valued for r ≥ 2.709 . Therefore the above inequality holds if and only if

(r^{2} − 2) ϕ(P_{ℓ−1}, r)^{2} < (r^{2} − 1) ϕ(P_{ℓ}, r) ϕ(P_{ℓ−2}, r) .

From Lemma 3 we get

ϕ(P_{n}, r) = \frac{1}{\sqrt{r^{2} − 4}} (r_{1}^{n+1} − r_{2}^{n+1}) ,

where

r_{1} = \frac{1}{2} (r + \sqrt{r^{2} − 4}) and r_{2} = \frac{1}{2} (r − \sqrt{r^{2} − 4})

are the roots of the equation x^{2} − r x + 1 = 0 . From the Vieta formulas,

r_{1} + r_{2} = r ; r_{1} r_{2} = 1

and therefore

r_{1}^{2} + r_{2}^{2} = (r_{1} + r_{2})^{2} − 2 r_{1} r_{2} = r^{2} − 2
r_{1}^{4} + r_{2}^{4} = (r_{1}^{2} + r_{2}^{2})^{2} − 2 r_{1}^{2} r_{2}^{2} = (r^{2} − 2)^{2} − 2 .

In view of the above, ϕ(B^{∗∗}, r) > 0 holds if and only if

\frac{1}{r^{2} − 4} (r^{2} − 2) (r_{1}^{ℓ} − r_{2}^{ℓ})^{2} < \frac{1}{r^{2} − 4} (r^{2} − 1) (r_{1}^{ℓ+1} − r_{2}^{ℓ+1})(r_{1}^{ℓ−1} − r_{2}^{ℓ−1})

if and only if

(r^{2} − 2) (r_{1}^{2ℓ} + r_{2}^{2ℓ} − 2) < (r^{2} − 1) [r_{1}^{2ℓ} + r_{2}^{2ℓ} − (r^{2} − 2)]

if and only if

r_{1}^{2ℓ} + r_{2}^{2ℓ} > (r^{2} − 2)(r^{2} − 3) .

We now demonstrate that for ℓ ≥ 2 the series a_{ℓ} = r_{1}^{2ℓ} + r_{2}^{2ℓ} strictly increases.

Because

r_{1}^{2ℓ} + r_{2}^{2ℓ} = \frac{r_{1}^{4ℓ} + 1}{r_{1}^{2ℓ}}

we get that

\frac{a_{ℓ+1}}{a_{ℓ}} = \frac{r_{1}^{4ℓ+4} + 1}{r_{1}^{4ℓ+2} + r_{1}^{2}}

will be greater than unity (in which case a_{ℓ} increases) if and only if

r_{1}^{4ℓ+4} + 1 > r_{1}^{4ℓ+2} + r_{1}^{2}

i.e., if

(r_{1}^{4ℓ+2} − 1) (r_{1}^{2} − 1) > 0

which is evidently obeyed since r_{1} > 1 .

We have previously shown that ϕ(B^{∗∗}, r) > 0 holds if and only if

r_{1}^{2ℓ} + r_{2}^{2ℓ} > (r^{2} − 2)(r^{2} − 3) .

Now, if this inequality is satisfied for ℓ = 2 it will be satisfied for all ℓ ≥ 2 .

For ℓ = 2 we get

r_{1}^{4} + r_{2}^{4} > (r^{2} − 2)(r^{2} − 3)

if and only if

(r^{2} − 2)^{2} − 2 > (r^{2} − 2)(r^{2} − 3)

if and only if r^{2} > 4 , which is evidently satisfied.

Thus we have demonstrated that

ϕ(B^{∗∗}, λ_{1}(B^{∗})) > 0

which, by Lemma 4, implies

λ_{1}(B^{∗∗}) < λ_{1}(B^{∗})

which, in turn, is sufficient for the validity of Theorem 2. It is interesting to note that we managed to verify the above inequalities without knowing the actual value of r = λ_{1}(B^{∗}) .

By this the proof of the Theorem 2 is completed.

REFERENCES

[1] D. C v e t k o v i ć, M. D o o b, H. S a c h s, Spectra of Graphs – Theory and Application, Academic Press, New York, 1980; 2nd revised ed.: Barth, Heidelberg, 1995.

[2] D. C v e t k o v i ć, P. R o w l i n s o n, On connected graphs with maximal index, Publ. Inst. Math. (Beograd) 44 (1988) 29–34.

[3] D. C v e t k o v i ć, P. R o w l i n s o n, The largest eigenvalue of a graph: A survey, Lin. Multilin. Algebra 28 (1990) 3–33.

[4] S.-G. G u o, The spectral radius of unicyclic and bicyclic graphs with n vertices and k pendant vertices, Lin. Algebra Appl., 408 (2005) 78–85.

Faculty of Science University of Kragujevac P. O. Box 60 34000 Kragujevac Serbia and Montenegro Department of Mathematics Yancheng Teachers College Yancheng 224002 Jiangsu P. R. China