# The Smallest Spectral Radius of Graphs with  a Given Clique Number

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

---

## Abstract

The first four smallest values of the spectral radius among all connected graphs with maximum clique sizeω
≥
2 are obtained.


---

## Body

## 1. Introduction

LetG
=
(
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
i
j
) is defined as n
×
n matrix (
a
i
j
), where a
i
j
=
1 if v
i is adjacent to v
j and a
i
j
=
0, otherwise. Denote by d
(
v
i
) or d
G
(
v
i
) the degree of the vertex v
i. It is well known that A
(
G
) is a real symmetric matrix. Hence, the eigenvalues of A
(
G
) can be ordered as
(1)
λ
1
(
G
)
≥
λ
2
(
G
)
≥
⋯
≥
λ
n
(
G
)
,
respectively. The largest eigenvalue of A
(
G
) is called the spectral radius of G, denoted by ρ
(
G
). It is easy to see that if G is connected, then A
(
G
) is nonnegative irreducible matrix. By the Perron-Frobenius theory, ρ
(
G
) has multiplicity one and exists a unique positive unit eigenvector corresponding to ρ
(
G
). We refer to such an eigenvector corresponding to ρ
(
G
) as the Perron vector of G.Denote byP
n and C
n the path and the cycle on n vertices, respectively. The characteristic polynomial of A
(
G
) is det
⁡
(
x
I
-
A
(
G
)
), which is denoted by Φ
(
G
) or Φ
(
G
,
x
). Let X be an eigenvector of G corresponding to ρ
(
G
). It will be convenient to associate with X a labelling of G in which vertex v
i is labelled x
i (or x
v
i). Such labellings are sometimes called “valuation” [1].The investigation on the spectral radius of graphs is an important topic in the theory of graph spectra. The recent developments on this topic also involve the problem concerning graphs with maximal or minimal spectral radius, signless Laplacian spectral radius, and Laplacian spectral radius, of a given class of graphs, respectively. The spectral radius of a graph plays an important role in modeling virus propagation in networks [2]. It has been shown that the smaller the spectral radius, the larger the robustness of a network against the spread of viruses [3]. In [4], the first three smallest values of the Laplacian spectral radii among all connected graphs with maximum clique size ω are given. And, in [5], it is shown that among all connected graphs with maximum clique size ω the minimum value of the spectral radius is attained for a kite graph P
K
n
-
ω
,
ω, where P
K
n
-
ω
,
ω is a graph on n vertices obtained from the path P
n
-
ω and the complete graph K
ω by adding an edge between an end vertex of P
n
-
ω and a vertex of K
ω (shown in Figure 1). Furthermore, in this paper, the first four smallest values of the spectral radius are obtained among all connected graphs with maximum clique size ω.Figure 1
Kite graphP
K
n
-
ω
,
ω.LetI
n
,
ω be the set of all connected graphs of order n with a maximum clique size ω, where 2
≤
ω
≤
n. It is easy to see that I
ω
,
ω
=
{
K
ω
}. By direct calculation, we have ρ
(
K
ω
)
=
ω
-
1. If G
∈
I
ω
+
1
,
ω, then, from the Perron-Frobenius theorem, the first ω
-
1 smallest values of the spectral radius of I
ω
+
1
,
ω are P
K
1
,
ω
;
i (0
≤
i
≤
ω
-
2), respectively, where P
K
1
,
ω
;
i is the graph obtained from P
K
1
,
ω by adding i (0
≤
i
≤
ω
-
2) edges. So in the following, we consider that n
≥
ω
+
2.


## 2. Preliminaries

In order to complete the proof of our main result, we need the following lemmas.Lemma 1 (see [6]).
Letv be a vertex of the graph G. Then the inequalities
(2)
λ
1
(
G
)
≥
λ
1
(
G
-
v
)
≥
λ
2
(
G
)
≥
λ
2
(
G
-
v
)
≥
⋯
≥
λ
n
-
1
(
G
-
v
)
≥
λ
n
(
G
)
hold. If G is connected, then λ
1
(
G
)
>
λ
1
(
G
-
v
).For the spectral radius of a graph, by the well-known Perron-Frobenius theory, we have the following.Lemma 2.
LetG be a connected graph and H a proper subgraph of G. Then ρ
(
H
)
<
ρ
(
G
).Lemma 3 (see [6, 7]).
LetG be a graph on n vertices, then
(3)
ρ
(
G
)
≤
max
⁡
{
d
(
v
)
:
v
∈
V
(
G
)
}
.
The equality holds if and only if G is a regular graph.Letv be a vertex of a graph G and suppose that two new paths P
=
v
(
v
k
+
1
)
v
k
⋯
v
2
v
1 and Q
=
v
(
u
l
+
1
)
u
l
⋯
u
2
u
1 of lengths k and l (k
≥
l
≥
1) are attached to G at v
(
=
v
k
+
1
=
u
l
+
1
), respectively, to form a new graph G
k
,
l (shown in Figure 2), where v
1
,
v
2
,
…
,
v
k and u
1
,
u
2
,
…
,
u
l are distinct. Let
(4)
G
k
+
1
,
l
-
1
=
G
k
,
l
-
u
1
u
2
+
v
1
u
1
.
We call that G
k
+
1
,
l
-
1 is obtained from G
k
,
l by grafting an edge (see Figure 2).Figure 2
Grafting an edge.Lemma 4 (see [8, 9]).
LetG be a connected graph on n
≥
2 vertices and v is a vertex of G. Let G
k
,
l and G
k
+
1
,
l
-
1 (k
≥
l
≥
1) be the graphs as defined above. Then ρ
(
G
k
,
l
)
>
ρ
(
G
k
+
1
,
l
-
1
).Letv be a vertex of the graph G and N
(
v
) the set of vertices adjacent to v.Lemma 5 (see [10, 11]).
LetG be a connected graph, and let 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 v
v
i and adding the edges u
v
i (1
≤
i
≤
s). If x
u
≥
x
v, then ρ
(
G
)
<
ρ
(
G
*
).Lemma 6 (see [12]).
Letv be a vertex of G, 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
(5)
Φ
(
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
).An internal path of a graphG is a sequence of vertices v
1
,
v
2
,
…
,
v
k with k
≥
2 such that(1)
the vertices in the sequence are distinct (except possiblyv
1
=
v
k);
(2)
v
i is adjacent to v
i
+
1, (i
=
1,2
,
…
,
k
-
1);
(3)
the vertex degreesd
(
v
i
) satisfy d
(
v
1
)
≥
3
,
d
(
v
2
)
=
⋯
=
d
(
v
k
-
1
)
=
2 (unless k
=
2) and d
(
v
k
)
≥
3.LetW
n be the tree on n vertices obtained from P
n
-
4 by attaching two new pendant edges to each end vertex of P
n
-
4, respectively.Lemma 7 (see [13]).
Suppose thatG
≠
W
n is a connected graph and u
v is an edge on an internal path of G. Let G
u
v be the graph obtained from G by subdivision of the edge u
v. Then ρ
(
G
u
v
)
<
ρ
(
G
).


## 3. Main Results

LetH
1 be the graph obtained from K
ω and a path P
4
:
v
1
v
2
v
3
v
4 by joining a vertex of K
ω and a nonpendant vertex, say, v
2, of P
4 by a path with length 2 and let H
2 be the graph obtained from K
ω by attaching two pendant edges at two different vertices of K
ω (see Figure 3).Figure 3
H
1 and H
2.Lemma 8.
LetH
1 and H
2 be the graphs defined as above (see Figure 3). If ω
≥
3, then ρ
(
H
2
)
>
ρ
(
H
1
).Proof.
For5
≥
ω
≥
3, by direct computations, we have ρ
(
H
2
)
>
ρ
(
H
1
). In the following, we suppose that ω
≥
6. From Lemma 6, we have
(6)
Φ
(
H
1
)
=
(
x
+
1
)
ω
-
2
[
x
7
-
(
ω
-
2
)
x
6
-
(
ω
+
4
)
x
5
hhhhhhhhhhh
+
(
5
ω
-
10
)
x
4
+
(
4
ω
+
1
)
x
3
hhhhhhhhhhh
-
(
5
ω
-
10
)
x
2
-
(
2
ω
-
1
)
x
+
ω
-
2
]
=
(
x
-
ω
+
2
)
ω
-
2
g
1
(
x
)
.
Φ
(
H
2
)
=
(
x
+
1
)
ω
-
3
[
x
5
-
(
ω
-
3
)
x
4
-
(
2
ω
-
1
)
x
3
hhhhhhhhhhh
+
(
ω
-
5
)
x
2
+
(
2
ω
-
3
)
x
-
ω
+
3
]
=
(
x
+
1
)
ω
-
3
g
2
(
x
)
.
By direct calculation, we have(7)
g
1
(
ω
-
1
+
1
ω
2
)
=
-
ω
3
+
2
ω
2
+
6
ω
+
13
ω
+
26
ω
2
-
54
ω
3
+
26
ω
4
+
34
ω
5
-
54
ω
6
+
20
ω
7
+
20
ω
8
-
25
ω
9
+
5
ω
10
+
6
ω
11
-
5
ω
12
+
1
ω
14
-
20
<
0
;
g
1
(
ω
-
1
+
2
ω
2
)
=
ω
4
-
6
ω
3
+
7
ω
2
+
26
ω
+
66
ω
+
166
ω
2
-
416
ω
3
+
224
ω
4
+
432
ω
5
-
832
ω
6
+
320
ω
7
+
560
ω
8
-
800
ω
9
+
160
ω
10
+
384
ω
11
-
320
ω
12
+
128
ω
14
-
91
>
0
;
g
2
(
ω
-
1
+
2
ω
2
)
=
-
2
ω
+
12
ω
-
18
ω
2
-
8
ω
3
+
48
ω
4
-
48
ω
5
-
8
ω
6
+
64
ω
7
-
32
ω
8
+
32
ω
10
<
0
.
From Lemmas 1 and 3, we have ω
>
ρ
(
H
1
)
≥
ρ
(
K
ω
)
=
ω
-
1
≥
λ
2
(
H
1
) and ω
>
ρ
(
H
2
)
≥
ρ
(
K
ω
)
=
ω
-
1. Then from (7) we have ρ
(
H
2
)
>
ω
-
1
+
(
2
/
ω
2
)
>
ρ
(
H
1
).LetP
K
n
-
ω
,
ω
i be the graph obtained from the kite graph P
K
n
-
ω
-
1
,
ω (see Figure 1) and an isolated vertex v
n by adding an edge v
n
v
i (ω
+
1
≤
i
≤
n
-
1) (see Figure 4). It is easy to see that P
K
5
,
ω
ω
+
2
=
H
1 and P
K
n
-
ω
,
ω
n
-
1
=
P
K
n
-
ω
,
ω.Figure 4
GraphP
K
n
-
ω
,
ω
i, where i
=
ω
+
1
,
…
,
n
-
1.LetP
K
¯
n
-
ω
,
ω
n
-
2
=
P
K
n
-
ω
,
ω
n
-
2
+
v
n
-
1
v
n (see Figure 5).Figure 5
GraphP
K
¯
n
-
ω
,
ω
n
-
2.Lemma 9.
LetP
K
n
-
ω
,
ω
i be the graphs defined as above (see Figure 4). Then
(8)
ρ
(
P
n
)
<
ρ
(
P
K
n
-
2,2
n
-
2
)
<
ρ
(
C
n
)
=
ρ
(
W
n
)
<
ρ
(
P
K
n
-
2,2
n
-
3
)
,
hhhh
(
n
≥
10
)
.Proof.
Clearly,P
n
=
P
2
n
-
2,0, P
K
n
-
2,2
2
=
P
2
n
-
3,1. From Lemma 4, we have
(9)
ρ
(
P
n
)
<
ρ
(
P
K
n
-
2,2
n
-
2
)
<
ρ
(
W
n
)
=
2
=
ρ
(
C
n
)
.
For n
≥
10, from Lemma 2, we have ρ
(
P
K
n
-
2,2
n
-
3
)
≥
ρ
(
P
K
8,2
7
)
≈
2.00659
>
ρ
(
C
n
).LetG
1
=
P
K
n
-
3,3
n
-
3
-
v
n
-
1
v
n
-
2
+
v
n
-
3
v
n
-
1, let G
2
=
P
K
n
-
3,3
n
-
3
+
v
n
-
1
v
n, and let C
n
-
1,1 be the graph obtained from C
n
-
1 and an isolated vertex by adding an edge between some vertex of C
n
-
1 and the isolated vertex (see Figure 6).Figure 6
GraphsG
1, G
2, C
n
-
1,1.Theorem 10.
Among all connected graphs onn vertices with maximum clique size ω
=
2 and n
≥
10, the first four smallest spectral radii are exactly obtained for P
n, P
K
n
-
2,2
n
-
2, C
n, W
n, and P
K
n
-
2,2
n
-
3, respectively.Proof.
LetG be a connected graph with maximum clique size ω
=
2 and n
≥
10 vertices. From Lemma 9, we have ρ
(
P
n
)
<
ρ
(
P
K
n
-
2,2
n
-
2
)
<
ρ
(
W
n
)
=
ρ
(
C
n
)
<
ρ
(
P
K
n
-
2,2
n
-
3
). Thus, we only need to prove that ρ
(
G
)
>
ρ
(
P
K
n
-
2,2
n
-
3
) if G
≠
P
n, P
K
n
-
2,2
n
-
2, W
n, C
n, P
K
n
-
2,2
n
-
3. If G is a tree, note that G
≠
P
n, P
K
n
-
2,2
n
-
2, W
n, P
K
n
-
2,2
n
-
3, then, from Lemma 4, we have ρ
(
G
)
>
ρ
(
P
K
n
-
2,2
n
-
3
). If G contains some cycle as a subgraph, then, from Lemmas 2 and 7, we have ρ
(
G
)
≥
ρ
(
C
n
-
1,1
)
>
ρ
(
P
K
n
-
2,2
n
-
3
).Lemma 11.
LetP
K
n
-
ω
,
ω
i, P
K
¯
n
-
ω
,
ω
n
-
2, G
1 and G
2 be the graphs defined as above (see Figures 4, 5, and 6). Then
(10)
ρ
(
P
K
n
-
3,3
n
-
4
)
<
min
⁡
{
ρ
(
P
K
¯
n
-
3,3
n
-
2
)
,
ρ
(
G
1
)
,
ρ
(
G
2
)
}
,
hhhhhhhhhhhhhhhhhhhhhh
(
n
≥
8
)
.Proof.
For8
≤
n
≤
11, by direct calculation, we have ρ
(
P
K
n
-
3,3
n
-
4
)
<
ρ
(
G
1
). If n
≥
12, from Lemmas 2 and 7, we have 2.23601
<
ρ
(
P
K
8,3
)
<
ρ
(
P
K
n
-
3,3
n
-
4
)
<
ρ
(
P
K
9,3
8
)
<
2.23808. From Lemma 6, we have
(11)
Φ
(
P
K
n
-
3,3
n
-
4
)
=
(
x
5
-
4
x
3
+
3
x
)
Φ
(
P
K
n
-
8,3
)
-
(
x
4
-
2
x
2
)
Φ
(
P
K
n
-
8,3
-
v
n
-
5
)
=
f
1
(
x
)
Φ
(
P
K
n
-
8,3
)
-
f
2
(
x
)
Φ
(
P
K
n
-
8,3
-
v
n
-
5
)
,
Φ
(
G
1
)
=
(
x
5
-
4
x
3
)
Φ
(
P
K
n
-
8,3
)
-
(
x
4
-
3
x
2
)
Φ
(
P
K
n
-
8,3
-
v
n
-
5
)
=
f
3
(
x
)
Φ
(
P
K
n
-
8,3
)
-
f
4
(
x
)
Φ
(
P
K
n
-
8,3
-
v
n
-
5
)
.
Then we have
(12)
f
3
(
x
)
Φ
(
P
K
n
-
3,3
n
-
4
)
-
f
1
(
x
)
Φ
(
G
1
)
=
(
f
1
(
x
)
f
4
(
x
)
-
f
2
(
x
)
f
3
(
x
)
)
Φ
(
P
K
n
-
8,3
-
v
n
-
5
)
=
(
-
x
7
+
7
x
5
-
9
x
3
)
Φ
(
P
K
n
-
8,3
-
v
n
-
5
)
=
R
1
(
x
)
Φ
(
P
K
n
-
8,3
-
v
n
-
5
)
.
For 2.23601
<
x
<
2.23808, we have
(13)
f
1
(
x
)
>
2.2360
1
5
-
4
×
2.2380
8
3
+
3
×
2.23601
≈
17
>
0
;
f
3
(
x
)
>
2.2360
1
5
-
4
×
2.2380
8
3
≈
11
>
0
;
R
1
(
x
)
>
-
2.2380
8
7
+
7
×
2.2360
1
5
-
9
×
2.2380
8
3
≈
9
>
0
.
Note that from Lemma 2, ρ
(
P
K
n
-
8,3
-
v
n
-
5
)
<
ρ
(
P
K
n
-
3,3
n
-
4
) and 2.23601
<
ρ
(
P
K
n
-
3,3
n
-
4
)
<
2.23808. Then, we have
(14)
f
3
(
x
)
Φ
(
P
K
n
-
3,3
n
-
4
)
>
f
1
(
x
)
Φ
(
G
1
)
,
h
h
h
h
i
x
∈
[
ρ
(
P
K
n
-
3,3
n
-
4
)
,
2.23808
)
.
Thus, ρ
(
P
K
n
-
3,3
n
-
4
)
<
ρ
(
G
1
). By similar method, we have for n
≥
8
(15)
ρ
(
P
K
n
-
3,3
n
-
4
)
<
ρ
(
P
K
¯
n
-
3,3
n
-
2
)
,
ρ
(
P
K
n
-
3,3
n
-
4
)
<
ρ
(
G
2
)
.LetH
3 be the graph obtained from K
ω by attaching two pendant edges at some vertex of K
ω; let H
4 be the graph obtained from K
ω and P
2 by adding two edges between two vertices of K
ω and two end vertices of P
2 (see Figure 7).Figure 7
GraphsH
3, H
4, and F
g.Theorem 12.
Among all connected graphs onn vertices with maximum clique size ω
=
3 and n
≥
9, the first four smallest spectral radii are exactly obtained for P
K
n
-
3,3, P
K
n
-
3,3
n
-
2, P
K
n
-
3,3
n
-
3, P
K
n
-
3,3
n
-
4, respectively.Proof.
LetG be a connected graph with maximum clique size ω
=
3 and n
≥
9 vertices. From Lemmas 2 and 7, we have
(16)
ρ
(
P
K
n
-
3,3
n
-
4
)
>
ρ
(
P
K
n
-
3,3
n
-
3
)
>
ρ
(
P
K
n
-
3,3
n
-
2
)
>
ρ
(
P
K
n
-
3,3
)
.
Thus, we only need to prove that ρ
(
G
)
>
ρ
(
P
K
n
-
3,3
n
-
4
) if G
≠
P
K
n
-
3,3, P
K
n
-
3,3
n
-
2, P
K
n
-
3,3
n
-
3, P
K
n
-
3,3
n
-
4.
We distinguish the following three cases.
Case  1. If there exist at least two vertices outside of K
3 that are adjacent to some vertices of K
3, then we have that G contains either H
2 (ω
=
3) or H
3 (ω
=
3) as a proper subgraph. If G contains H
2 (ω
=
3) as a proper subgraph, from Lemmas 2 and 7, we have
(17)
ρ
(
G
)
>
ρ
(
H
2
)
≈
2.30278
>
ρ
(
P
K
6,3
5
)
≈
2.26542
>
ρ
(
P
K
n
-
3,3
n
-
4
)
,
(
ω
=
3
)
.
If G contains H
3 (ω
=
3) as a proper subgraph, from Lemmas 2 and 7, we have
(18)
ρ
(
G
)
>
ρ
(
H
3
)
≈
2.34292
>
ρ
(
P
K
6,3
5
)
>
ρ
(
P
K
n
-
3,3
n
-
4
)
,
(
ω
=
3
)
.
Case  2. Suppose that there exists a vertex, say, u, which does not belong to K
3, such that u is adjacent to at least two vertices of K
3. Then G contains C
4
* as a proper subgraph, where C
4
* is obtained from C
4 by adding an edge between two disjoint vertices. From Lemmas 2 and 7, we have
(19)
ρ
(
G
)
>
ρ
(
C
4
*
)
≈
2.56155
>
ρ
(
P
K
6,3
5
)
>
ρ
(
P
K
n
-
3,3
n
-
4
)
.
Case  3. Suppose that there uniquely exists a vertex u which does not belong to K
3 such that u is adjacent to a vertex of K
3. We distinguish the following two cases.
Subcase 1. Suppose that G
-
V
(
K
3
) is a tree. If there exist two vertices u
,
r
∈
V
(
G
-
V
(
K
3
)
) such that d
(
u
)
≥
3 and d
(
r
)
≥
3, then, from Lemmas 2, 4, and 7, we have ρ
(
G
)
>
ρ
(
P
K
n
-
3,3
n
-
4
). If there exists only one vertex u
∈
V
(
G
-
V
(
K
3
)
) such that d
(
u
)
≥
4, then, from Lemmas 2, 7, and 11, we have ρ
(
G
)
≥
ρ
(
G
1
)
>
ρ
(
P
K
n
-
3,3
n
-
4
). If there exists exactly one vertex u
∈
V
(
G
-
V
(
K
3
)
) such that d
(
u
)
=
3, note that G
≠
P
K
n
-
3,3
n
-
2, P
K
n
-
3,3
n
-
3, P
K
n
-
3,3
n
-
4, then from Lemmas 2 and 7 we have ρ
(
G
)
>
ρ
(
P
K
n
-
3,3
n
-
4
).
Subcase 2. Suppose that G
-
V
(
K
3
) contains cycle C
g as a subgraph. If g
=
3,4, then, from Lemmas 2, 7 and 11, we have ρ
(
G
)
≥
ρ
(
P
K
¯
n
-
3,3
n
-
2
)
>
ρ
(
P
K
n
-
3,3
n
-
4
) or ρ
(
G
)
≥
ρ
(
G
2
)
>
ρ
(
P
K
n
-
3,3
n
-
4
). If g
≥
5, then, from Lemma 2, we can construct a graph F
g from G by deleting vertices such that ρ
(
G
)
≥
ρ
(
F
g
), where F
g is the graph obtained from K
3 and a cycle C
g by joining a vertex of K
3 and a vertex of C
g with a path and |
V
(
F
g
)
|
≤
n (see Figure 7). Suppose that C
g is labelled v
1
,
v
2
,
…
,
v
g satisfying v
i
v
i
+
1
∈
E
(
C
g
), (1
≤
i
≤
g
-
1), v
1
v
g
∈
E
(
C
g
), and d
(
v
1
)
=
3. Then, from Lemmas 2 and 7, we have ρ
(
F
g
-
v
2
v
3
)
>
ρ
(
P
K
n
-
3,3
n
-
4
). Thus, we have ρ
(
G
)
>
ρ
(
P
K
n
-
3,3
n
-
4
).Lemma 13.
LetP
K
n
-
ω
,
ω
i and P
K
¯
n
-
ω
,
ω
n
-
2 be the graphs defined as above (see Figures 4 and 5). Then ρ
(
P
K
n
-
ω
,
ω
n
-
3
)
>
ρ
(
P
K
¯
n
-
ω
,
ω
n
-
2
) (ω
≥
4).Proof.
LetX
=
(
x
1
,
x
2
,
…
,
x
n
)
T be the Perron vector of P
K
¯
n
-
ω
,
ω
n
-
2, where x
i corresponds to v
i. It is easy to prove that x
n
=
x
n
-
1. From A
X
=
ρ
(
P
K
¯
n
-
ω
,
ω
n
-
2
)
X, we have
(20)
x
n
-
2
=
(
ρ
(
P
K
¯
n
-
ω
,
ω
n
-
2
)
-
1
)
x
n
,
x
n
-
3
=
[
ρ
(
P
K
¯
n
-
ω
,
ω
n
-
2
)
(
ρ
(
P
K
¯
n
-
ω
,
ω
n
-
2
)
-
1
)
-
2
]
x
n
.
From Lemma 2, for ω
≥
4 we have ρ
(
P
K
¯
n
-
ω
,
ω
n
-
2
)
≥
ρ
(
K
ω
)
=
ω
-
1
≥
3. Then
(21)
ρ
(
P
K
n
-
ω
,
ω
n
-
3
)
-
ρ
(
P
K
¯
n
-
ω
,
ω
n
-
2
)
≥
X
T
A
(
P
K
n
-
ω
,
ω
n
-
3
)
X
-
X
T
A
(
P
K
¯
n
-
ω
,
ω
n
-
2
)
X
=
2
x
n
(
x
n
-
3
-
x
n
-
2
-
x
n
)
=
2
[
ρ
(
P
K
¯
n
-
ω
,
ω
n
-
2
)
(
ρ
(
P
K
¯
n
-
ω
,
ω
n
-
2
)
-
2
)
-
2
]
x
n
≥
2
x
n
>
0
.
So, ρ
(
P
K
n
-
ω
,
ω
n
-
3
)
>
ρ
(
P
K
¯
n
-
ω
,
ω
n
-
2
).LetM
ω
2 (ω
≥
4) be the graph as shown in Figure 8.Figure 8
GraphM
ω
2.Theorem 14.
Among all connected graphs onn vertices with maximum clique size ω
≥
4 and n
≥
ω
+
5, the first four smallest spectral radii are exactly obtained for P
K
n
-
ω
,
ω, P
K
n
-
ω
,
ω
n
-
2, P
K
¯
n
-
ω
,
ω
n
-
2, P
K
n
-
ω
,
ω
n
-
3, respectively.Proof.
LetG be a connected graph with maximum clique size ω
≥
4 and n
≥
ω
+
5 vertices. Suppose that K
ω is a maximum clique of G. From Lemmas 2, 4, and 13, we have
(22)
ρ
(
P
K
n
-
ω
,
ω
n
-
3
)
>
ρ
(
P
K
¯
n
-
ω
,
ω
n
-
2
)
>
ρ
(
P
K
n
-
ω
,
ω
n
-
2
)
>
ρ
(
P
K
n
-
ω
,
ω
)
.
Thus, we only need to prove that ρ
(
G
)
>
ρ
(
P
K
n
-
ω
,
ω
n
-
3
) if G
≠
P
K
n
-
ω
,
ω, P
K
n
-
ω
,
ω
n
-
2, P
K
¯
n
-
ω
,
ω
n
-
2, P
K
n
-
ω
,
ω
n
-
3. We distinguish the following three cases.
Case  1. If there exist at least two vertices outside of K
ω that are adjacent to some vertices of K
ω, then G contains either H
2 or H
3 as a proper subgraph. If G contains H
2 as a proper subgraph, from Lemmas 2, 7, and 8, we have
(23)
ρ
(
G
)
>
ρ
(
H
2
)
>
ρ
(
H
1
)
≥
ρ
(
P
K
n
-
ω
,
ω
n
-
3
)
.
If G contains H
3 as a proper subgraph, from Lemmas 2, 5, 7, and 8, we have
(24)
ρ
(
G
)
>
ρ
(
H
3
)
>
ρ
(
H
2
)
>
ρ
(
H
1
)
≥
ρ
(
P
K
n
-
ω
,
ω
n
-
3
)
.
Case  2. Suppose that there exists a vertex, say, u, which does not belong to K
ω, such that u is adjacent to at least two vertices of K
ω. From Lemmas 2, 7, and 8, we have
(25)
ρ
(
G
)
>
ρ
(
M
ω
2
)
>
ρ
(
H
4
)
>
ρ
(
H
2
)
>
ρ
(
H
1
)
≥
ρ
(
P
K
n
-
ω
,
ω
n
-
3
)
.
Case  3. Suppose that there uniquely exists a vertex u which does not belong to K
ω such that u is adjacent to a vertex of K
ω. If G
-
V
(
K
ω
) is a tree, note that G
≠
P
K
n
-
ω
,
ω, P
K
n
-
ω
,
ω
n
-
2, P
K
n
-
ω
,
ω
n
-
3, then, from Lemmas 2, 4, and 7, we have ρ
(
G
)
>
ρ
(
P
K
n
-
ω
,
ω
n
-
3
). Suppose that G
-
V
(
K
ω
) contains cycle C
g as a subgraph. If g
=
3, note that G
≠
P
K
¯
n
-
ω
,
ω
n
-
2, then, from Lemmas 2 and 7, we have ρ
(
G
)
>
ρ
(
G
*
)
>
ρ
(
P
K
n
-
ω
,
ω
n
-
3
), where G
*
=
P
K
n
-
ω
,
ω
n
-
3
+
v
n
-
1
v
n. If g
≥
4, then by the similar reasoning as that of Subcase 2 of Case 3 of Theorem 12, we have ρ
(
G
)
>
ρ
(
P
K
n
-
ω
,
ω
n
-
3
).Lemma 15.
LetH
3 and H
4 be the graphs defined as above (see Figure 7). Then
(26)
ρ
(
H
4
)
>
ρ
(
H
3
)
(
ω
≥
3
)
.Proof.
LetX
=
(
x
1
,
x
2
,
…
,
x
n
)
T be the Perron vector of H
3, where x
i corresponds to v
i. From A
X
=
ρ
(
H
3
)
X, we have
(27)
ρ
(
H
3
)
x
1
=
x
2
,
ρ
(
H
3
)
x
2
=
2
x
1
+
(
ω
-
1
)
x
ω
,
ρ
(
H
3
)
x
ω
=
(
ω
-
2
)
x
ω
+
x
2
.
From above equations, we have
(28)
ρ
3
(
H
3
)
-
(
ω
-
2
)
ρ
2
(
H
3
)
-
(
ω
+
1
)
ρ
(
H
3
)
+
2
ω
-
4
=
0
.
Let
(29)
r
1
(
x
)
=
x
3
-
(
ω
-
2
)
x
2
-
(
ω
+
1
)
x
+
2
ω
-
4
.
Then
(30)
r
1
(
ω
-
1
)
=
-
2
<
0
.
For x
>
ω
-
1 and ω
≥
3, we have
(31)
r
1
′
(
x
)
=
3
x
2
-
2
(
ω
-
2
)
x
-
(
ω
+
1
)
>
0
.
Note that ρ
(
H
3
)
>
ρ
(
K
ω
)
=
ω
-
1. From (30) and (31), we have ρ
(
H
3
) which is the largest root of equation r
1
(
x
)
=
0. Similarly, we have ρ
(
H
4
) which is the largest root of equation
(32)
r
2
(
x
)
=
x
3
-
(
ω
-
1
)
x
2
-
2
x
+
2
ω
-
4
=
0
.
Then we have, for x
>
ω
-
1,
(33)
r
1
(
x
)
-
r
2
(
x
)
=
x
2
-
(
ω
-
1
)
x
>
0
.
Thus, we have ρ
(
H
3
)
<
ρ
(
H
4
).Theorem 16.
LetG be a graph on n vertices with maximum clique size ω
≥
3 and n
=
ω
+
2. Let P
K
2
,
ω, H
2, H
3, and H
4 be the graphs defined as above (see Figures 1, 3 and 7). The first four smallest spectral radii are obtained for P
K
2
,
ω, H
2, H
3, H
4, respectively.Proof.
From Lemmas2, 5, 8, and 15, we have
(34)
ρ
(
H
4
)
>
ρ
(
H
3
)
>
ρ
(
H
2
)
>
ρ
(
H
1
)
>
ρ
(
P
K
2
,
ω
)
.
Thus, we only need to prove that, for G
≠
P
K
2
,
ω, H
2, H
3, and H
4, ρ
(
G
)
>
ρ
(
H
4
). We distinguish the following two cases.
Case  1. Suppose that there exists exactly one vertex outside of K
ω that is adjacent to at least two vertices of K
ω. Then G contains M
ω
2 (see Figure 8) as a subgraph. From Lemmas 2 and 7, we have ρ
(
M
ω
2
)
>
ρ
(
H
4
).
Case  2. Suppose that the two vertices outside of K
ω that are all adjacent to some vertices of K
ω. Note that G
≠
H
2, H
3, H
4. Then G contains one of graphs H
¯
3 and M
ω
2 as a subgraph, where H
¯
3 is obtained from H
3 by adding an edge between two pendant vertices. From Lemma 5, we have ρ
(
G
)
≥
ρ
(
H
¯
3
)
>
ρ
(
H
4
). From Lemmas 2 and 7, ρ
(
G
)
>
ρ
(
M
ω
2
)
>
ρ
(
H
4
).LetH
5 be the graph obtained from H
2 and an isolated vertex by adding an edge between a pendant vertex of H
2 and the isolated vertex; let P
K
¯
3
,
ω
ω
+
1 and H
6 be the graphs as shown in Figure 9.Figure 9
GraphsP
K
¯
3
,
ω
ω
+
1, H
5, and H
6.Lemma 17.
LetP
K
¯
3
,
ω
ω
+
1 and H
5 be the graphs defined as above (see Figure 9). Then
(35)
ρ
(
H
5
)
>
ρ
(
P
K
¯
3
,
ω
ω
+
1
)
,
(
ω
≥
4
)
.Proof.
LetX
=
(
x
1
,
x
2
,
…
,
x
n
)
T be the Perron vector of P
K
¯
3
,
ω
ω
+
1, where x
i corresponds to v
i. It is easy to see that x
1
=
x
5. From A
X
=
ρ
(
P
K
¯
3
,
ω
ω
+
1
)
X, we have
(36)
ρ
(
P
K
¯
3
,
ω
ω
+
1
)
x
1
=
x
1
+
x
2
,
ρ
(
P
K
¯
3
,
ω
ω
+
1
)
x
2
=
2
x
1
+
x
3
,
ρ
(
P
K
¯
3
,
ω
ω
+
1
)
x
3
=
x
2
+
(
ω
-
1
)
x
4
,
ρ
(
P
K
¯
3
,
ω
ω
+
1
)
x
4
=
x
3
+
(
ω
-
2
)
x
4
.
From above equations, we have
(37)
x
2
=
(
ρ
(
P
K
¯
3
,
ω
ω
+
1
)
-
1
)
x
1
,
x
4
=
ρ
2
(
P
K
¯
3
,
ω
ω
+
1
)
-
ρ
(
P
K
¯
3
,
ω
ω
+
1
)
-
2
ρ
(
P
K
¯
3
,
ω
ω
+
1
)
-
ω
+
2
x
1
.
Then for ω
≥
4, we have
(38)
ρ
(
H
5
)
-
ρ
(
P
K
¯
3
,
ω
ω
+
1
)
≥
X
T
A
(
H
5
)
X
-
X
T
A
(
P
K
¯
3
,
ω
ω
+
1
)
X
=
2
x
1
(
x
4
-
x
2
-
x
1
)
=
2
(
ω
-
3
)
ρ
(
P
K
¯
3
,
ω
ω
+
1
)
-
2
ρ
(
P
K
¯
3
,
ω
ω
+
1
)
-
ω
+
2
x
1
>
0
.
The result follows.Lemma 18.
LetH
5 and H
6 be the graphs defined as above (see Figure 9). Then
(39)
ρ
(
H
6
)
>
ρ
(
H
5
)
,
(
ω
≥
4
)
.Proof.
Forω
=
4, by direct calculation, we have ρ
(
H
6
)
>
ρ
(
H
5
). In the following, we suppose that ω
≥
5. Then, from Lemmas 2 and 3, we have ω
>
ρ
(
H
5
)
>
ρ
(
K
ω
)
=
ω
-
1
≥
4. Let X
=
(
x
1
,
x
2
,
…
,
x
n
)
T be the Perron vector of H
5, where x
i corresponds to v
i. From A
X
=
ρ
(
H
5
)
X, we have
(40)
ρ
(
H
5
)
x
1
=
x
2
,
ρ
(
H
5
)
x
2
=
x
1
+
x
3
,
ρ
(
H
5
)
x
3
=
x
2
+
x
4
+
(
ω
-
2
)
x
6
,
ρ
(
H
5
)
x
4
=
x
3
+
x
5
+
(
ω
-
2
)
x
6
,
ρ
(
H
5
)
x
5
=
x
4
,
ρ
(
H
5
)
x
6
=
x
3
+
x
4
+
(
ω
-
3
)
x
6
.
From above equations, we have for ω
>
ρ
(
H
5
)
>
ω
-
1
≥
4,
(41)
x
6
=
ρ
2
(
H
5
)
-
1
ρ
(
H
5
)
-
ω
+
3
x
1
+
(
ρ
2
(
H
5
)
+
ρ
(
H
5
)
)
(
ρ
2
(
H
5
)
-
1
)
-
ρ
2
(
H
5
)
(
ρ
(
H
5
)
-
ω
+
3
)
(
ρ
2
(
H
5
)
+
ρ
(
H
5
)
-
1
)
x
1
>
ρ
2
(
H
5
)
-
1
3
x
1
>
ρ
(
H
5
)
x
1
=
x
2
.
Then, from Lemma 5, we have ρ
(
H
6
)
=
ρ
(
H
5
-
v
1
v
2
+
v
1
v
6
)
>
ρ
(
H
5
).LetH
7 be the graph obtained from H
3 and an isolated vertex by adding an edge between v
ω and the isolated vertex; let H
8 be the graph obtained from H
3 and an isolated vertex by adding an edge between v
2 and the isolated vertex; let H
9 be the graph obtained from H
3 and an isolated vertex by adding an edge between one pendant vertex and the isolated vertex; and let H
10 be the graph obtained from P
K
3
,
ω
ω
+
1 and an isolated vertex by adding an edge between v
ω
+
1 and the isolated vertex (see Figure 10).Figure 10
GraphsH
7, H
8, H
9, H
10.Theorem 19.
LetP
K
3
,
ω, P
K
3
,
ω
ω
+
1, P
K
¯
3
,
ω
ω
+
1, and H
5 be the graphs defined as above (see Figures 1, 4, 5, and 9). Among all connected graphs on n vertices with maximum clique size ω and n
=
ω
+
3 (ω
≥
4), the first four smallest spectral radii are obtained for P
K
3
,
ω, P
K
3
,
ω
ω
+
1, P
K
¯
3
,
ω
ω
+
1, and H
5, respectively.Proof.
From Lemmas2, 4, and 17, we have
(42)
ρ
(
H
5
)
>
ρ
(
P
K
¯
3
,
ω
ω
+
1
)
>
ρ
(
P
K
3
,
ω
ω
+
1
)
>
ρ
(
P
K
3
,
ω
)
.
Thus, we only need to prove that ρ
(
G
)
>
ρ
(
H
5
) if G
≠
P
K
3
,
ω, P
K
3
,
ω
ω
+
1, P
K
¯
3
,
ω
ω
+
1, and H
5. We distinguish the following four cases.
Case  1. There exists exactly one vertex outside of K
ω that is adjacent to only one vertex of K
ω. Then G must be one of graphs P
K
3
,
ω, P
K
3
,
ω
ω
+
1, and P
K
¯
3
,
ω
ω
+
1.
Case  2. There exists one vertex outside of K
ω that is adjacent to at least two vertices of K
ω. Then G contains M
ω
2 (see Figure 8) as a proper subgraph. From Lemmas 2 and 7, we have ρ
(
G
)
>
ρ
(
M
ω
2
)
>
ρ
(
H
5
).
Case  3. If there exactly exist two vertices outside of K
ω that are adjacent to some vertices of K
ω, then G contains H
5 or H
9 (see Figures 9 and 10) as a subgraph. If G contains H
9 as a subgraph, then, from Lemmas 2 and 5, we have ρ
(
G
)
≥
ρ
(
H
9
)
>
ρ
(
H
5
). If G contains H
5 as a subgraph, note that G
≠
H
5, then, from Lemma 2, we have ρ
(
G
)
>
ρ
(
H
5
).
Case  4. If there exist three vertices outside of K
ω that are adjacent to some vertices of K
ω, then G contains one of graphs H
6, H
7, and H
8 (see Figures 9 and 10) as a subgraph. From Lemmas 5 and 18, we have ρ
(
H
8
)
>
ρ
(
H
7
)
>
ρ
(
H
6
)
>
ρ
(
H
5
). Then, from Lemma 2, we have ρ
(
G
)
>
ρ
(
H
5
).Lemma 20.
LetP
K
n
-
ω
,
ω
i and P
K
¯
4
,
ω
ω
+
2 be the graphs defined as above (see Figures 4 and 5). Then
(43)
ρ
(
P
K
4
,
ω
ω
+
1
)
>
ρ
(
P
K
¯
4
,
ω
ω
+
2
)
,
(
ω
≥
4
)
.Proof.
From Lemma6, we have
(44)
Φ
(
P
K
¯
4
,
ω
ω
+
2
)
=
(
x
4
-
4
x
2
-
2
x
+
1
)
Φ
(
K
ω
)
-
(
x
3
-
3
x
-
2
)
Φ
(
K
ω
-
1
)
=
f
5
(
x
)
Φ
(
K
ω
)
-
f
6
(
x
)
Φ
(
K
ω
-
1
)
;
Φ
(
P
K
4
,
ω
ω
+
1
)
=
(
x
4
-
3
x
2
+
1
)
Φ
(
K
ω
)
-
(
x
3
-
x
)
Φ
(
K
ω
-
1
)
=
f
7
(
x
)
Φ
(
K
ω
)
-
f
8
(
x
)
Φ
(
K
ω
-
1
)
.
Then, we have
(45)
f
7
(
x
)
Φ
(
P
K
¯
4
,
ω
ω
+
2
)
-
f
5
(
x
)
Φ
(
P
K
4
,
ω
ω
+
1
)
=
(
f
5
(
x
)
f
8
(
x
)
-
f
6
(
x
)
f
7
(
x
)
)
Φ
(
K
ω
-
1
)
=
(
x
5
-
5
x
3
-
4
x
2
+
2
x
+
2
)
Φ
(
K
ω
-
1
)
=
R
2
(
x
)
Φ
(
K
ω
-
1
)
.
For x
>
ω
-
1 (ω
≥
4), we have
(46)
f
5
(
x
)
>
0
,
f
7
(
x
)
>
0
,
R
2
(
x
)
>
0
,
Φ
(
K
ω
-
1
)
>
0
.
From Lemma 2, we have ρ
(
P
K
¯
4
,
ω
ω
+
2
)
>
ρ
(
K
ω
)
=
ω
-
1 and ρ
(
P
K
4
,
ω
ω
+
1
)
>
ρ
(
K
ω
)
=
ω
-
1. Thus, for x
>
ω
-
1 (ω
≥
4), we have f
7
(
x
)
Φ
(
P
K
¯
4
,
ω
ω
+
2
)
-
f
5
(
x
)
Φ
(
P
K
4
,
ω
ω
+
1
)
>
0. Then ρ
(
P
K
4
,
ω
ω
+
1
)
>
ρ
(
P
K
¯
4
,
ω
ω
+
2
), (ω
≥
4).Lemma 21.
LetP
K
n
-
ω
,
ω
i and H
2 be the graphs defined as above (see Figures 3 and 4). Then
(47)
ρ
(
H
2
)
>
ρ
(
P
K
4
,
ω
ω
+
1
)
,
(
ω
≥
3
)
.Proof.
Forω
=
3,4
,
5, by direct calculation, we have ρ
(
H
2
)
>
ρ
(
P
K
4
,
ω
ω
+
1
). In the following, we suppose that ω
≥
6. From Lemma 6, we have
(48)
Φ
(
P
K
4
,
ω
ω
+
1
)
=
(
x
+
1
)
ω
-
2
[
x
6
-
(
ω
-
2
)
x
5
-
(
ω
+
3
)
x
4
hhhhhhhhhhh
+
(
4
ω
-
8
)
x
3
+
(
3
ω
-
1
)
x
2
h
h
h
h
h
h
h
h
h
h
h
i
-
(
2
ω
-
4
)
x
-
ω
+
1
]
=
(
x
+
1
)
ω
-
2
g
3
(
x
)
.
For ω
≥
6, we have
(49)
g
3
(
ω
-
1
+
1
ω
2
)
=
-
ω
2
-
13
ω
+
4
ω
2
+
17
ω
3
-
24
ω
4
+
6
ω
5
+
14
ω
6
-
16
ω
7
+
2
ω
8
+
5
ω
9
-
4
ω
10
+
1
ω
12
+
7
<
0
;
g
3
(
ω
-
1
+
2
ω
2
)
=
ω
3
-
5
ω
2
+
2
ω
-
58
ω
+
20
ω
2
+
108
ω
3
-
192
ω
4
+
48
ω
5
+
192
ω
6
-
256
ω
7
+
32
ω
8
+
160
ω
9
-
128
ω
10
+
64
ω
12
+
24
>
0
.
From Lemmas 1 and 3, we have ω
>
ρ
(
P
K
4
,
ω
ω
+
1
)
≥
ρ
(
K
ω
)
=
ω
-
1
≥
λ
2
(
P
K
4
,
ω
ω
+
1
). Then from (49) we have ω
-
1
+
2
/
ω
2
>
ρ
(
P
K
4
,
ω
ω
+
1
)
>
ω
-
1
+
1
/
ω
2. From the proof of Lemma 8, we have ρ
(
H
2
)
>
ω
-
1
+
2
/
ω
2 (ω
≥
6). The result follows.Theorem 22.
Among all connected graphs onn vertices with maximum clique size ω and n
=
ω
+
4 (ω
≥
4), the first four smallest spectral radii are obtained for P
K
4
,
ω, P
K
4
,
ω
ω
+
2, P
K
¯
4
,
ω
ω
+
2, and P
K
4
,
ω
ω
+
1 (see Figures 1, 4, and 5), respectively.Proof.
LetG be a connected graph with maximum clique size ω
≥
4 and n
=
ω
+
4 vertices. Suppose that K
ω is a maximum clique of G. From Lemmas 2, 4, and 20, we have
(50)
ρ
(
P
K
4
,
ω
ω
+
1
)
>
ρ
(
P
K
¯
4
,
ω
ω
+
2
)
>
ρ
(
P
K
4
,
ω
ω
+
2
)
>
ρ
(
P
K
4
,
ω
)
.
Thus, we only need to prove that ρ
(
G
)
>
ρ
(
P
K
4
,
ω
ω
+
1
) if G
≠
P
K
4
,
ω, P
K
4
,
ω
ω
+
2, P
K
¯
4
,
ω
ω
+
2, P
K
4
,
ω
ω
+
1. We distinguish the following three cases.
Case  1. There exists exactly one vertex outside of K
ω that is adjacent to one vertex of K
ω.
Subcase 1. Suppose that G
-
V
(
K
ω
) is a tree. If G contains exactly one pendant vertex, then G
=
P
K
4
,
ω. If G contains exactly two pendant vertices, then G
=
P
K
4
,
ω
ω
+
1 or G
=
P
K
4
,
ω
ω
+
2. If G contains three pendant vertices, then G
=
H
10 (see Figure 10). From Lemma 4, we have ρ
(
H
10
)
>
ρ
(
P
K
4
,
ω
ω
+
1
).
Subcase 2. Suppose that G
-
V
(
K
ω
) contains a cycle. If G
-
V
(
K
ω
) contains C
4, then G contains H
11 as a subgraph, where H
11 is obtained from P
K
4
,
ω
ω
+
1 by adding an edge between two pendant vertices. From Lemma 2, we have ρ
(
H
11
)
>
ρ
(
P
K
4
,
ω
ω
+
1
). If G
-
V
(
K
ω
) does not contain C
4, then G
=
P
K
¯
4
,
ω
ω
+
2 or G contains P
K
¯
3
,
ω
ω
+
1 as a proper subgraph. From Lemmas 2 and 7, we have ρ
(
P
K
¯
3
,
ω
ω
+
1
)
>
ρ
(
H
11
)
>
ρ
(
P
K
4
,
ω
ω
+
1
). Note that G
≠
P
K
¯
4
,
ω
ω
+
2. Thus, we have ρ
(
G
)
>
ρ
(
P
K
4
,
ω
ω
+
1
).
Case  2. There exists at least one vertex outside of K
ω that is adjacent to at least two vertices of K
ω. Then G contains M
ω
2 (see Figure 8) as a subgraph. From Lemmas 2, 7, and 21, we have ρ
(
G
)
>
ρ
(
M
ω
2
)
>
ρ
(
H
2
)
>
ρ
(
P
K
4
,
ω
ω
+
1
).
Case  3. There exist at least two vertices outside of K
ω that are adjacent to some vertices of K
ω. Then G contains H
2 or H
3 as a subgraph (see Figures 3 and 7). From Lemmas 2, 5, and 21, we have ρ
(
H
3
)
>
ρ
(
H
2
)
>
ρ
(
P
K
4
,
ω
ω
+
1
). Thus, from Lemma 2, we have ρ
(
G
)
>
ρ
(
P
K
4
,
ω
ω
+
1
).


## 4. Conclusion

In this paper, the first four graphs, which have the smallest values of the spectral radius among all connected graphs of ordern with maximum clique size ω
≥
2, are determined.



---

*Source: 232153-2014-07-13.xml*