The Minimal Spectral Radius with Given Independence Number

Abstract

In this paper, we determine the graphs which have the minimal spectral radius among all the connected graphs of order n and the independence number $\lceil \frac{n}{2}\rceil -1.$

1 Introduction

Let G be a simple, connected and undirected graph of order n with vertex set V(G) and edge set E(G). For a graph G, a vertex subset S is independent if the induced subgraph G[S] has no edges. The maximum size of an independent set in G is called the independence number of G and denoted by $\alpha (G)$. For the vertex set $\{v_1,v_2,\ldots ,v_n\}$ of G, the adjacency matrix $A(G)=(a_{ij})$ of G is defined as the $n\times n$ matrix whose ij-entry is 1 if $v_i$ and $v_j$ are adjacent or 0 otherwise. Since A(G) is a real symmetric matrix, all its eigenvalues are real. The largest eigenvalue of A(G) is called the spectral radius of G and denoted by $\rho (G)$. By Perron-Frobenius Theorem, $\rho (G)$ is simple and positive.

Many studies about the relation between the spectral radius and the independence number have been done. In particular, it is important to find a bound of the spectral radius of graphs satisfying certain conditions and to classify the corresponding extremal graphs. In [3], Das and Mohanty gave an upper bound for the spectral radius of bi-block graphs with given independence numbers, where a block of a graph is a maximal connected subgraph having no cut-vertex and a bi-block graph is a connected graph each of whose blocks is a complete bipartite graph. Lou and Guo [9] extended the result of [3] and proved that among all bipartite graphs with given independence number $\alpha$, the maximum spectral radius is uniquely attained by the complete bipartite graph $K_{\alpha , n-\alpha }$.

On the other hand, determining the graphs with the minimum spectral radius among connected graphs with given independence number is considered to be a tough problem. ([13, §4.4]). A graph with minimum spectral radius among a given class of graphs is called a minimizer graph. Let ${\mathbb {G}}_{n,\alpha }$ be the set of simple connected graphs of order n with independence number $\alpha$. In [14], Xu, Hong, Shu and Zhai determined the minimizer graphs with the independence number $\alpha =1,2,\lceil \frac{n}{2}\rceil ,\lceil \frac{n}{2}\rceil +1,n-3,n-2,n-1$. Du and Shi in [4] determined the minimizer graph for $\alpha =3,4$ and $n=k\alpha$ for some integer k and Jin and Zhang in [8] extended this results for all $\alpha$ and $n=k\alpha$. In [9], Lou and Guo proved that the minimizer graph in ${\mathbb {G}}_{n, \alpha }$ must be a tree if $\alpha \ge \lceil \frac{n}{2}\rceil$. They also determined the extremal graphs when $\alpha =n-4$. Later, Hu, Huang and Lou [7] gave a construction of the minimizer graphs for $\alpha \ge \lceil \frac{n}{2}\rceil$.

In this paper, we determine the minimizer graph when $\alpha = \lceil \frac{n}{2}\rceil -1$. To state our main theorem, we fix notations. Let $C_n$ be the cycle of length n and let $P_n$ be the path of length n. Let B(m, p, q) be the graph obtained by attaching $C_m$ and $C_q$ at each end vertex of the path $P_p$. (See Fig. 2) The main theorem of this paper is the following.

Theorem 1.1

Let G be the minimizer graph in $\displaystyle {\mathbb {G}}_{n,\lceil \frac{n}{2}\rceil -1}$ where $n\ge 7$ and let $k=\lceil \frac{n}{3}\rceil$. Then

$$\begin{aligned} G \cong {\left\{ \begin{array}{ll} C_n, &{}{} \text{ if }\ n \text{ is } \text{ odd }\\ B(k+1,k-1,k+1), &{}{} \text{ if }\ n\equiv 0\ (mod~6)\\ B(k,k,k), &{}{} \text{ if }\ n\equiv 2\ (mod~6)\\ B(k-1,k+1,k-1), &{}{} \text{ if }\ n\equiv 4\ (mod~6) \end{array}\right. } \end{aligned}$$

Remark 1.2

For completeness, we state results for $n\le 6$, which can be checked easily. The complete graph $K_3$ and $K_4$ are the only graph in ${\mathbb {G}}_{3,1}$ and ${\mathbb {G}}_{4,1}$, respectively. The minimizer graph in ${\mathbb {G}}_{5,2}$ is $C_5$ and in ${\mathbb {G}}_{6,2}$ is B(3, 1, 3).

This paper is organized as follows. In Sect. 2, we review necessary results. In Sect. 3, we study the spectral radius of bicyclic graphs. In Sect. 4, we prove Theorem 1.1. For undefined terms or notations of graph theory, see West [15]. For basic properties of spectral graph theory, see Brouwer and Haemers [1] or Godsil and Royle [5].

2 Preliminaries

In this section, we introduce relevant tools and results.

Lemma 2.1

(Perron-Frobenius theorem). Let G be a connected graph and A be the adjacency matrix of G. Then we have the following.

• 1. The spectral radius $\rho (G)$ of G is a positive simple eigenvalue of A

• 2. There is a unique positive unit eigenvector of A corresponding to $\rho (G)$. This vector is called the Perron vector of G.

• 3. If there exists a nonzero vector y with $y\ge 0$ and a number $\sigma$ such that $Ay\le \sigma y$ and $Ay\ne \sigma y$, then $y>0$ and $\rho (G)<\sigma$.

Lemma 2.2

([2, Interlacing Theorem]). Let G be a graph with n vertices and eigenvalues $\lambda _1\ge \lambda _2\ge \cdots \ge \lambda _n$ and let H be an induced subgraph of G with m vertices and eigenvalues $\mu _1\ge \mu _2\ge \cdots \ge \mu _m$. Then for $1\le i\le m,$

$$\begin{aligned}\lambda _i\ge \mu _i\ge \lambda _{n-m+i}.\end{aligned}$$

In other words, the eigenvalues of H interlace the eigenvalues of G.

Lemma 2.3

([2, Theorem 1.3.10]) Let G be a connected graph. Then deleting an edge of G strictly decreases its spectral radius.

By Lemma 2.3, the characterization of the graph having maximal spectral radius in ${\mathbb {G}}_{n,\alpha }$ is immediate. The join of graphs G and H, written as $G \vee H$, is the graph union of G and H together with all the edges joining each vertex of G to each vertex of H.

Theorem 2.4

([9]). Let $G\in {\mathbb {G}}_{n,\alpha }$. Then $\rho (G)\le \rho (K_{n-\alpha }\vee \alpha K_1)$ with equality if and only if $G\cong K_{n-\alpha }\vee \alpha K_1$.

We introduce operations on graphs which decreases the spectral radius. An internal path of a graph is a sequence of vertices $u_1,u_2,\cdots ,u_k$ such that all $u_i$ are distinct (except possibly $u_1=u_k$), the degree $d(u_i)$ satisfy

$$\begin{aligned}d(u_1)\ge 3,\ d(u_2)=\cdots =d(u_{k-1})=2, \ d(u_k)\ge 3,\end{aligned}$$

and $u_i$ is adjacent to $u_{i+1}$ for $i=1,2,\cdots ,k-1.$ Note that two adjacent vertices with degree at least 3 form an internal path.

Lemma 2.5

([6, Proposition 2.4]). Let G be a graph not isomorphic to the graph ${\tilde{D}}_n$ depicted in Fig. 1. Then the spectral radius strictly decreases after inserting a vertex of degree 2 to an internal path of G (i.e. after deleting an edge uv in an internal path and adding a new vertex w and two new edges uw and wv).

Fig. 1

${\tilde{D}}_n$

Thus, by Lemmas 2.2 and 2.5, removing a vertex outside of an internal path and reinserting it into the internal path strictly decreases the spectral radius while the number of vertices remains unchanged. We will repeatedly use this operation.

For the Perron vector x of a graph G, we denote by $x_u$ the component of x corresponding to a vertex $u\in V(G)$. A cut edge is a single edge whose removal disconnects the graph.

Lemma 2.6

([16, Theorem 1]). Let G be a connected graph with the Perron vector x. Let u, v be two vertices of G. Suppose that $u_1,u_2,\ldots ,$ $u_s(1\le s \le d(u))$ are some vertices of $N_G(u){\setminus } N_G(v)$. Let $G^*$ be the graph obtained from G by deleting the edges $(u,u_i)$ and adding the edges $(v,u_i)(1\le i\le s)$. If $x_u\le x_v$, then $\rho (G)<\rho (G^*)$.

Lemma 2.7

([7, Lemma 3.5]). Let G be a connected graph with the Perron vector x. Suppose that $vw_1$ is a cut edge of G, $N_G(v)=\{w_1,w_2,\ldots ,w_t\}(t\ge 3)$ and $x_{w_1}=\min _{w\in N_G(v)}{x_w}$. Let $G'$ be a graph obtained from G by replacing v with two new vertices $v',v''$ and adding new edges $v'w_1,v'w_2,\ldots ,v'w_s$ and $v''w_1, v''w_{s+1},v''w_{s+2},\ldots ,v''w_t$ for some $2\le s\le t-1$. Then $\rho (G')\le \rho (G)$, with equality if and only if $t=3$ and $x_{w_1}=x_{w_2}=x_{w_3}$.

3 Spectral Radius of Bicyclic Graphs

A connected graph G is called a unicyclic graph if $|E(G)|=|V(G)|$ and a bicyclic graph if $|E(G)|=|V(G)|+1$. For even n, we will see that the minimizer graphs in $\displaystyle {\mathbb {G}}_{n,\lceil \frac{n}{2}\rceil -1}$ are bicyclic graphs. In this section, we present results on the spectral radius of bicyclic graphs, which will be used in the proof of our main theorem.

Definition 3.1

Let m, p, q be positive integers.

• 1. Let P(m, p, q) be the graph obtained by identifying each end vertex of the path graphs $P_m$, $P_p$ and $P_q$. We assume at most one of m, p, q is one.

• 2. Let C(m, q) be the graph obtained by identifying a vertex of the cycle graphs $C_m$ and $C_q$. We assume $m,q\ge 3$.

• 3. Let B(m, p, q) be the graph obtained by attaching $C_m$ and $C_q$ at each end vertex of the path $P_p$. We assume $m,q\ge 3$ and $p\ge 1$.

These graphs are depicted in Fig. 2. Each of m, p, q is the number of edges for a path or a cycle. The number of vertices of P(m, p, q) and B(m, p, q) is $m+p+q-1$ and that of C(m, q) is $m+q-1$. We label each vertex of P(m, p, q) and B(m, p, q) as shown in Fig. 2.

Fig. 2

The bicyclic graphs P(m, p, q), C(m, q) and B(m, p, q)

Note that a graph G with $|E(G)|\ge |V(G)|+1$ contains a subgraph isomorphic to either P(m, p, q), C(m, q) or B(m, p, q) for some integer m, p, q. We review results of [10] and [11].

Lemma 3.2

([11]). For any integers $m\ge 3$ and $p\ge 1$, $\rho (P(m,p,m))=\rho (B(m,p,m))$.

In [11], Simić and Kocić proved Lemma 3.2 by observing that the Perron vectors and the spectral radii of the two graphs should satisfy the same equations. We remark that Lemma 3.2 can also be seen by using equitable partition. Namely, the vertex sets

$$\begin{aligned} {}&{} \{u_0,v_0\}, \{u_1,v_1,u_{m-1},v_{m-1}\},\ldots ,\{u_{\lfloor \frac{m}{2}\rfloor }, v_{\lfloor \frac{m}{2}\rfloor },u_{\lceil \frac{m}{2}\rceil },v_{\lceil \frac{m}{2}\rceil }\}, \\{}&{} \quad \{w_{1},w_{p-1}\}, \ldots \{w_{\lfloor \frac{p}{2}\rfloor },w_{\lceil \frac{p}{2}\rceil } \} \end{aligned}$$

on both graphs form equitable partitions having the same quotient matrix. Hence, they have the same spectral radius.

Lemma 3.3

([11]).

• 1. If $m+p+q$ is fixed, $\rho (P(m,p,q))$ decreases as $\max (m,p,q)-\min (m,p,q)$ decreases.

• 2. If $m+q$ is fixed, $\rho (C(m,q))$ decreases as $\max (m,q)-\min (m,q)$ decreases.

However, for the graphs B(m, p, q), the difference between parameters is not sufficient to compare their spectral radii, unless we fix the middle parameter.

Lemma 3.4

([10]). If p and $m+q$ are fixed, $\rho (B(m,p,q))$ decreases as $\max (m,q)-\min (m,q)$ decreases.

Let ${\mathbb {B}}_n$ be the set of all bicyclic graphs with order n. By Lemmas 2.2 and 2.5, the minimizer graph in ${\mathbb {B}}_n$ has no vertices of degree one, because otherwise we can remove that vertex and reinsert it to an internal path to get a graph with less spectral radius. Also, by Lemmas 3.3 and 3.4, it is expected that the minimizer graph is either P(m, p, q) or B(m, p, q) where the difference $\max (m,p,q)-\min (m,p,q)$ is as small as possible. In [11], Simić proved that this is the case.

Lemma 3.5

([10]). Assume $n\ge 7$ and let $k=\lceil \frac{n}{3}\rceil$. The minimizer graphs in ${\mathbb {B}}_n$ are $P(k,n+1-2k,k)$ and $B(k,n+1-2k,k)$.

Now, we present a few comparison results between the spectral radius of bicyclic graphs. Let

$$\begin{aligned} x=(x_{u_0},\ldots ,x_{u_{m-1}},x_{w_1},\ldots ,x_{w_{p-1}},x_{v_0},\ldots ,x_{v_{q-1}})^T \end{aligned}$$

be the Perron vector of the graph B(m, p, q) and let $\rho =\rho (B(m,p,q))$. Then we have

$$\begin{aligned} \rho x_v=\sum _{u \sim v} x_u. \end{aligned}$$

(1)

We will use the following elementary lemma to determine x and $\rho$.

Lemma 3.6

([10, Lemma 1]). Define

$$\begin{aligned}f_i(t,k,a,b)=\frac{b\sinh {it}+a\sinh {(k-i)t}}{\sinh {kt}}.\end{aligned}$$

The difference equation

$$\begin{aligned} \rho x_{i+1}=x_{i}+x_{i+2}\,(i=0,\ldots k-2)\quad \text {with}\quad x_0=a,x_k=b \end{aligned}$$

(2)

has the solution $x_i=f_i(t_{\rho },k,a,b)$, where $t_{\rho }=\ln (\frac{\rho +\sqrt{\rho ^2-4}}{2})$ or equivalently $\rho =2\cosh {t_{\rho }}$.

Assume $x_{u_0}=a$ and $x_{v_0}=b$. By Lemma 3.6, we have

$$\begin{aligned} x_{u_i}&= f_i(t_\rho , m, a, a) \text { for }i =1, \ldots , m-1, \\ x_{w_i}&= f_i(t_\rho , p, a, b) \text { for }i =1, \ldots , p-1,\\ x_{v_i}&= f_i(t_\rho , q, b, b) \text { for }i =1, \ldots , q-1. \end{aligned}$$

The numbers a and b are determined by equations (1) at vertices $u_0$ and $v_0$, that is,

$$\begin{aligned} 2a\cosh {t_{\rho }}&=2f_1(t_{\rho },m,a,a)+f_1(t_{\rho },p,a,b),\\ 2b\cosh {t_{\rho }}&=2f_1(t_{\rho },q,b,b)+f_{p-1}(t_{\rho },p,a,b). \end{aligned}$$

Rearranging terms using the definition of $f_i$, we get

$$\begin{aligned} a \cosh {t_{\rho }} - f_1(t_{\rho },m,a,a) - \frac{1}{2} f_1(t_{\rho },p,a,a)&=-\frac{a-b}{2}\frac{\sinh {t_{\rho }}}{\sinh {pt_{\rho }}}, \end{aligned}$$

(3)

$$\begin{aligned} a \cosh {t_{\rho }} - f_1(t_{\rho },q,a,a) - \frac{1}{2} f_1(t_{\rho },p,a,a)&=\frac{a(a-b)}{2b}\frac{\sinh {t_{\rho }}}{\sinh {pt_{\rho }}}. \end{aligned}$$

(4)

Remark 3.7

Dividing both sides of (3), (4) by a and subtracting (3) from (4), we have

$$\begin{aligned} f_1(t_{\rho },m,1,1)-f_1(t_{\rho },q,1,1)=(a-b)\left( \frac{1}{2a}+\frac{1}{2b}\right) \frac{\sinh {t_{\rho }}}{\sinh {pt_{\rho }}}. \end{aligned}$$

It is easy to check that $f_1(t_{\rho },x,1,1)$ is strictly decreasing in x.( [10, Lemma 3]) Thus, if $m>q$ then $a<b$ and if $m=q$ then $a=b$.

The following is a slight modification of [10, Equation (11)].

Lemma 3.8

Let m, p be distinct positive integers greater than or equal to 3. Then,

$$\begin{aligned} \rho (B(m,p,m))<\rho (B(m,m,p)). \end{aligned}$$

Proof

For the Perron vector

$$\begin{aligned}x=(x_{u_0},\ldots ,x_{u_{m-1}},x_{w_1},\ldots ,x_{w_{m-1}},x_{v_0},\ldots ,x_{v_{p-1}})^T\end{aligned}$$

of B(m, m, p), let $x_{u_0}=a$ and $x_{v_0}=b$. Let $\sigma =\rho (B(m,m,p))$ and $t_{\sigma }=\ln (\frac{\sigma +\sqrt{\sigma ^2-4}}{2})$. By the above discussion, a and b must satisfy

$$\begin{aligned} 2a\cosh {t_{\sigma }}&=2f_1(t_{\sigma },m,a,a)+f_1(t_{\sigma },m,a,b),\\ 2b\cosh {t_{\sigma }}&=2f_1(t_{\sigma },p,b,b)+f_{p-1}(t_{\sigma },m,a,b). \end{aligned}$$

By rearranging terms as before, we have

$$\begin{aligned} a\cosh {t_{\sigma }} - f_1(t_{\sigma },m,a,a) - \frac{1}{2}f_1(t_{\sigma },m,a,a)&=-\frac{a-b}{2}\frac{\sinh {t_{\sigma }}}{\sinh {mt_{\sigma }}}, \end{aligned}$$

(5)

$$\begin{aligned} a\cosh {t_{\sigma }} - f_1(t_{\sigma },p,a,a) - \frac{1}{2}f_1(t_{\sigma },m,a,a)&=\frac{a(a-b)}{2b}\frac{\sinh {t_{\sigma }}}{\sinh {mt_{\sigma }}}. \end{aligned}$$

(6)

Consider a vector

$$\begin{aligned} x'=(x_{u_0}',\ldots ,x_{u_{m-1}}',x_{w_1}',\ldots ,x_{w_{p-1}}',x_{v_0}',\ldots ,x_{v_{m-1}}')^T \end{aligned}$$

constructed as

$$\begin{aligned}x_{u_i}'=x_{v_i}'=f_i(t_{\sigma },m,a,a)~\text {and}~ x_{w_j}'=f_j(t_{\sigma },p,a,a)\end{aligned}$$

for $i=0,1,\ldots ,m-1$ and $j=0,1,\ldots ,p-1$, which corresponds to the graph B(m, p, m). By construction, $\sigma x_v'= \sum _{u \sim v} x_u'$ for all degree two vertices v of B(m, p, m) by Lemma 3.6. We claim that $\sigma x_v'> \sum _{u \sim v} x_u'$ for $v= u_0$ or $v= v_0$, which implies $\rho (B(m,p,m))<\sigma$ by Theorem 2.1.

For $v=v_0$, we have

$$\begin{aligned} \sigma x_{v_0}'-\sum _{u \sim v_0}x_u'&= 2a \cosh {t_{\sigma }}-2 f_1(t_{\sigma },m,a,a)- f_{p-1}(t_{\sigma },p,a,a)\\&= a\left( \frac{a-b}{2b}-\frac{a-b}{2a}\right) \frac{\sinh {t_{\sigma }}}{\sinh {mt_{\sigma }}} \hspace{3em} \text {(by adding (5) and (6))}\\&= a(a-b)\left( \frac{1}{2b}-\frac{1}{2a}\right) \frac{\sinh {t_{\sigma }}}{\sinh {mt_{\sigma }}}\\&= \frac{(a-b)^2}{2b}\frac{\sinh {t_{\sigma }}}{\sinh {mt_{\sigma }}}. \end{aligned}$$

Since $\sigma >2$ by Lemma 4.1, $t_{\sigma }> 0$ and hence $\sigma x_{v_0}' > \sum _{u \sim v_0}x_u'$. By the same argument, we also have $\sigma x_{u_0}' > \sum _{u \sim u_0}x_u'$, which completes the proof. $\square$

Lemma 3.9

Let m, p, q be positive integers with $m\ge q \ge 3$. Then,

$$\begin{aligned} \rho (B(m,p,q))<\rho (C(m+p,q)). \end{aligned}$$

Proof

Let x be the Perron vector of B(m, p, q). By Remark 3.7, we have $x_{u_0}\le x_{v_0}$. Then Lemma 2.6 applies, where we take $u=u_0$, $v=v_0$, $s=1$ and $u_1\in N(u)\setminus N(v)$. $\square$

Lemma 3.10

Let m, p be positive integers with $\min (m,p)\ge q\ge 3$. Then,

$$\begin{aligned} \rho (B(m,p,q))\ge \rho (B(m,p-1,q+2)), \end{aligned}$$

with equality if and only if $m=p=q$.

Fig. 3

$\rho (G')\le \rho (G)$

Proof

We apply Lemma 2.7. Let G be the graph B(m, p, q) whose vertices are labelled as in Fig. 3 (a). Then $vw_1$ is a cut edge of G. For the Perron vector $x=(x_u\,|\,u\in V(G))$, we have

$$\begin{aligned} x_{w_1}&= f_1(t,p,x_v,x_z),\\ x_{w_2}&= f_1(t,q,x_v,x_v) = f_{q-1}(t,q,x_v,x_v) = x_{w_3} \end{aligned}$$

where $\rho (G)=2\cosh t$. Since $m\ge q$, we have $x_z\le x_v$ by Remark 3.7. Thus,

$$\begin{aligned} f_1(t,q,x_v,x_v) \ge f_1(t,p,x_v,x_v) \ge f_1(t,p,x_v,x_z), \end{aligned}$$

where the first inequality holds because $p\ge q$ and $f_1(t_{\rho },x,x_v,x_v)$ is strictly decreasing in x. Therefore $x_{w_1}=\min _{w\in N_G(v)}{x_w}$ and hence $\rho (B(m,p,q))\ge \rho (B(m,p-1,q+2))$ by Lemma 2.7.

The equality holds if and only if $x_{w_1}=x_{w_2}=x_{w_3}$. In the above inequality, this holds if and only if $x_z=x_v$ and $p=q$, or equivalently $m=p=q$. $\square$

4 Minimizer Graphs with Independence Number $\lceil \frac{n}{2}\rceil -1$

In this section, we determine the graphs with minimal spectral radius in $\displaystyle {\mathbb {G}}_{n,\lceil \frac{n}{2}\rceil -1}.$ Since $\alpha (T)\ge \lceil \frac{n}{2}\rceil$ for any tree T of order n, we will only consider non-tree graphs. In [12], Smith showed that the only graphs with spectral radius less than two are the finite simply-laced Dynkin diagrams and the only graphs with spectral radius equal to two are the extended simply-laced Dynkin diagrams. The only non-tree graph among them is the cycle $C_n$. Hence we have the following.

Lemma 4.1

([12]). Let G be a non-tree graph of order n. Then $\rho (G)\ge 2$ and $\rho (G)= 2$ if and only if G is the cycle $C_n$.

Since $\alpha (C_n)=\lceil \frac{n}{2}\rceil -1$ for odd n, the following is immediate.

Theorem 4.2

When n is odd, the minimizer graph in $\displaystyle {\mathbb {G}}_{n,\lceil \frac{n}{2}\rceil -1}$ is the cycle $C_n$.

From now on, we assume that n is even. By Lemma 2.3, the minimizer graphs should have as small number of edges as possible. For a unicyclic graph G of order n, we have $\alpha (G)\ge \lfloor \frac{n}{2}\rfloor$. ([15, Exercise 3.1.41]) Hence when n is even, $\alpha (G)\ge \frac{n}{2}>\lceil \frac{n}{2}\rceil -1$ for any unicyclic graph of order n.

Now we consider the bicyclic graphs. It is elementary to check the independence number of graphs P(m, p, q), C(m, q) and B(m, p, q).

Lemma 4.3

Let n be the order of the graph.

• 1. $\alpha (P(m,p,q))={\left\{ \begin{array}{ll} \lceil \frac{n}{2}\rceil -1, &{} \text{ if } \text{ exactly } \text{ two } \text{ of } m,p,q~\text {are odd},\\ \lceil \frac{n}{2}\rceil , &{} \text{ otherwise }. \end{array}\right. }$

• 2. $\alpha (C(m,q))={\left\{ \begin{array}{ll} \lceil \frac{n}{2}\rceil -1, &{} \text{ if } \text{ both } \text{ of } m,q~\text {are odd},\\ \lceil \frac{n}{2}\rceil , &{} \text{ otherwise }. \end{array}\right. }$

• 3. $\alpha (B(m,p,q))={\left\{ \begin{array}{ll} \lceil \frac{n}{2}\rceil -1, &{} \text{ if } \text{ at } \text{ least } \text{ two } \text{ of } m,p,q~\text {are odd},\\ \lceil \frac{n}{2}\rceil , &{} \text{ otherwise. } \end{array}\right. }$

When $k=\lceil \frac{n}{3}\rceil$ is odd, that is, when $n\equiv 2 \pmod {6}$, the graphs B(k, k, k) and P(k, k, k) are minimizer graphs in ${\mathbb {B}}_n$ by Lemma 3.5. By Lemma 4.3, $\alpha (B(k,k,k)) =\lceil \frac{n}{2}\rceil -1$ and $\alpha (P(k,k,k)) =\lceil \frac{n}{2}\rceil$. Hence we have the following.

Theorem 4.4

If $n\equiv 2 \pmod {6}$ and $n\ge 7$, the minimizer graph in $\displaystyle {\mathbb {G}}_{n,\lceil \frac{n}{2}\rceil -1}$ is isomorphic to B(k, k, k), where $k=\lceil \frac{n}{3}\rceil$.

Proof

A graph G in ${\mathbb {G}}_{n,\lceil \frac{n}{2}\rceil -1}$ has at least $n+1$ edges. Since removing an edge strictly decreases the spectral radius, $\rho (G)\ge \rho (H)$ for some bicyclic graph H. Hence $\rho (G)\ge \rho (H)\ge \rho (B(k,k,k))$ with equality if and only if $G= B(k,k,k)$. $\square$

Now, it remains to consider the cases $n\equiv 0$ or $4 \pmod {6}$. Our strategy is as follows. Since a graph G in ${\mathbb {G}}_{n, \lceil \frac{n}{2}\rceil -1}$ has more than n edges, G contains a minimal bicyclic subgraph, which is isomorphic to one of P(m, p, q), C(m, q) or B(m, p, q). We first show that if G contains either C(m, q) or P(m, p, q), then $\rho (G)$ is greater than that of the minimizer graph in Theorem 1.1. If G does not contain any of C(m, q) or P(m, p, q), all cycles in G are disjoint and G contains some B(m, p, q) as an induced subgraph. We prove that in this case the minimum spectral radius is attained by the minimizer graph in Theorem 1.1. Our main tool is Lemma 2.2 and Lemma 2.5. Namely, we take a minimal bicyclic subgraph and remove all vertices outside of it and reinsert them to appropriately chosen internal paths of the bicyclic subgraph. This process will decrease the spectral radius and we end up with the minimizer graph.

Remark 4.5

Note that when $n\equiv 0$ or $4 \pmod {6}$, we have $n=3k$ or $3k-2$, respectively, where $k=\lceil \frac{n}{3}\rceil$ is even. Hence if the bicyclic graphs P(m, p, q) and B(m, p, q) have order n, we have $m+p+q=3k+1$, or $3k-1$, respectively.

Proposition 4.6

Let n be an even integer with $n\ge 7$ and $k=\lceil \frac{n}{3}\rceil$ even. Suppose that a connected graph G of order n contains C(m, q) as a subgraph for some $m,q\ge 3$.

• 1. If $n\equiv 0 \pmod {6}$, then $\rho (G)>\rho (B(k+1,k-1,k+1))$.

• 2. If $n\equiv 4 \pmod {6}$, then $\rho (G)>\rho (B(k-1,k+1,k-1))$.

Proof

By Lemmas 2.2, 2.3 and 2.5, one can remove all vertices and edges outside of C(m, q) and reinsert vertices to one of the cycles, for example to the cycle of length q, in C(m, q) to get a graph with less spectral radius. Hence we have $\rho (C(m, n-m+1))\le \rho (G)$. Then,

$$\begin{aligned} \rho (G)\ge \rho (C(m, n-m+1))&\ge \rho \left( C\left( \frac{n}{2}+1,\frac{n}{2}\right) \right)&\text {(by Lemma } 3.3) \\&>\rho \left( B\left( \frac{n}{2},1,\frac{n}{2}\right) \right)&\text {(by Lemma }3.9) \\&=\rho \left( P\left( \frac{n}{2},1,\frac{n}{2}\right) \right)&\text {(by Lemma }3.2) \end{aligned}$$

Since $n\ge 7$, we have $n/2-1>2$. Thus when $n\equiv 0 \pmod {6}$, that is, when $n=3k$,

$$\begin{aligned} \rho \left( P\left( \frac{n}{2},1,\frac{n}{2}\right) \right) > \rho (P(k+1,k-1,k+1)) =\rho (B(k+1,k-1,k+1)), \end{aligned}$$

by Lemma 3.2 and Lemma 3.3. The case for $n\equiv 4 \pmod {6}$ is similar. $\square$

Proposition 4.7

Let n be an even integer with $n\ge 7$ and $k=\lceil \frac{n}{3}\rceil$ even. Suppose that a connected graph G of order n contains $P^*=P(m^*,p^*,q^*)$ as a subgraph for some integers $m^*,q^*\ge 2$ and $p^*\ge 1$.

• 1. If $n\equiv 0 \pmod {6}$ and $G\ncong P(k, k+1, k)$, then

  $$\begin{aligned} \rho (G)\ge \rho (B(k+1,k-1,k+1)) \end{aligned}$$

  with equality if and only if $G\cong P(k+1, k-1, k+1)$.

• 2. If $n\equiv 4 \pmod {6}$ and $G\ncong P(k, k-1, k)$, then

  $$\begin{aligned} \rho (G)\ge \rho (B(k-1,k+1,k-1)) \end{aligned}$$

  with equality if and only if $G\cong P(k-1, k+1, k-1)$.

Proof

Case 1. $n\equiv 0 \pmod {6}$

Note that we may assume that $P^* \ncong P(k, k+1, k)$. Indeed, if G contains $P(k, k+1, k)$ as a proper subgraph, that is, G is $P(k, k+1, k)$ with at least one extra edge between vertices, then one can see that G contains P(m, p, q) with $m+p+q < 3k+1$, which can be chosen to be $P^*$.

Suppose that $m^*+p^*+q^*=3k+1$. Since $P^* \ncong P(k, k+1, k)$, we have $\max (m^*,p^*,q^*)-\min (m^*,p^*,q^*)\ge 2$. Therefore, by Lemma 3.3 and Lemma 3.2,

$$\begin{aligned} \rho (G)\ge \rho (P^*)\ge \rho (P(k+1, k-1, k+1)) = \rho (B(k+1, k-1, k+1)). \end{aligned}$$

In this case, the equality holds if and only if $G\cong P(k+1, k-1, k+1)$.

Now suppose that $m^*+p^*+q^*< 3k+1$. If $(m^*,p^*,q^*)\ne (k,k,k)$, by removing all the vertices and edges outside of $P^*$ and reinserting vertices to the longest internal path in $P^*$, one can find $(m',p',q')$ such that $m'+p'+q'=3k+1$, $\max (m',p',q')-\min (m',p',q')\ge 2$ and $\rho (P(m',p',q'))<\rho (P^*)< \rho (G)$. Hence by the same argument as above, we have $\rho (G)> \rho (B(k+1, k-1, k+1))$.

Finally, if $(m^*,p^*,q^*)= (k,k,k)$, then by Lemma 3.2 and Lemma 3.10, we have

$$\begin{aligned} \rho (G) > \rho (P(k,k,k)) =\rho (B(k,k,k))= \rho (B(k,k-1, k+2)).\end{aligned}$$

Since $\rho (B(k,k-1, k+2)) >\rho (B(k+1,k-1, k+1))$, we are done.

Case 2. $n\equiv 4 \pmod {6}$

The proof is parallel to Case 1. We may assume that $P^* \ncong P(k, k-1, k)$. Then, by removing all the vertices and edges outside of $P^*$ and reinserting vertices to the longest internal path in $P^*$, one can find $(m',p',q')$ such that $m'+p'+q'=3k-1$, $\max (m',p',q')-\min (m',p',q')\ge 2$ and $\rho (P(m',p',q'))\le \rho (P^*)\le \rho (G)$. Thus

$$\begin{aligned}\rho (G)\ge \rho (P(m',p',q'))\ge \rho (P(k-1, k+1, k-1)) = \rho (B(k-1, k+1, k-1)). \end{aligned}$$

The equality holds if and only if $G\cong P(k-1, k+1, k-1)$. Therefore, the proof is complete. $\square$

By Lemma 4.3, $P(k, k+1, k)$ and $P(k+1, k-1, k+1)$ in the case $n\equiv 0 \pmod {6}$ and $P(k, k-1, k)$ and $P(k-1, k+1, k-1)$ in the case $n\equiv 4 \pmod {6}$ are not in ${\mathbb {G}}_{n,\lceil \frac{n}{2}\rceil -1}$. Hence by Proposition 4.6 and Proposition 4.7, we now assume that the graph G does not contain C(m, q) or P(m, p, q) as a subgraph. This condition is equivalent to the condition that all cycles in G are mutually disjoint.

Proposition 4.8

Let n be an even integer with $n\ge 7$ and $k=\lceil \frac{n}{3}\rceil$ even. Let $G\in \displaystyle {\mathbb {G}}_{n,\lceil \frac{n}{2}\rceil -1}$. Suppose that the cycles in G are mutually disjoint.

• 1. If $n\equiv 0 \pmod {6}$, then

  $$\begin{aligned} \rho (G)\ge \rho (B(k+1,k-1,k+1)) \end{aligned}$$

  with equality if and only if $G \cong B(k+1,k-1,k+1)$.

• 2. If $n\equiv 4 \pmod {6}$, then

  $$\begin{aligned} \rho (G)\ge \rho (B(k-1,k+1,k-1)) \end{aligned}$$

  with equality if and only if $G \cong B(k-1,k+1,k-1)$.

Proof

Since $G\in \displaystyle {\mathbb {G}}_{n,\lceil \frac{n}{2}\rceil -1}$ has at least $n+1$ edges, G contains at least two disjoint cycles. So, G contains $B^*=B(m^*,p^*,q^*)$ for some integers $m^*,q^*\ge 3$ and $p^*\ge 1$. We choose $B^*$ having the minimum $p^*$ so that $B^*$ is an induced subgraph of G.

Case 1. $n\equiv 0 \pmod {6}$

Subcase 1a. $m^*+p^*+q^*=n+1=3k+1$.

Since $B^*$ is an induced subgraph of G, we have $G=B^*=B(m^*,p^*,q^*)$ and moreover $m^*,p^*,q^*$ are all odd by Lemma 4.3.

First, assume that $p^*= k+1$. Then $(m^*, q^*)\ne (k,k)$ because k is even and hence $|m^*-q^*|\ge 2$. Thus,

$$\begin{aligned} \rho (G)= \rho (B(m^*,k+1,q^*))&\ge \rho (B(k+1,k+1,k-1))&\text {(by Lemma }3.4) \\&>\rho (B(k+1,k-1,k+1))&\text {(by Lemma }3.8) \end{aligned}$$

Now assume $p^*\ne k+1$. Then we have $|\frac{m^*+q^*}{2}-p^*|\ge 2$ with equality if and only if $(m^*,p^*,q^*)=(k+1, k-1, k+1)$. So,

$$\begin{aligned} \rho (G)= \rho (B(m^*,p^*,q^*))&\ge \rho (B(\frac{m^*+q^*}{2},p^*,\frac{m^*+q^*}{2}))&\text {(by Lemma }3.4) \\&=\rho (P(\frac{m^*+q^*}{2},p^*,\frac{m^*+q^*}{2}))&\text {(by Lemma }3.2) \\&\ge \rho (P(k+1,k-1,k+1))&\text {(by Lemma }3.3) \\&= \rho (B(k+1,k-1,k+1)).&\text {(by Lemma }3.2) \end{aligned}$$

Subcase 1b. $m^*+p^*+q^*<3k+1$.

First assume that $p^*\ne k$ or $k+1$. Then it is not hard to see that by removing all vertices outside of $B^*$ and reinserting them to appropriately chosen internal paths in $B^*$, one can find $(m',p',q')$ such that $m'+p'+q'=3k+1$, $p'$ is odd, $p'\ne k+1$ and $\rho (B(m',p',q'))<\rho (B^*)< \rho (G)$. Then we have $|\frac{m'+q'}{2}-p'|\ge 2$ with equality if and only if $(m',p',q')=(k+1, k-1, k+1)$. Thus by the similar argument as above,

$$\begin{aligned} \rho (G) >\rho (B(m',p',q'))\ge \rho (B(k+1,k-1,k+1)). \end{aligned}$$

Now assume that $p^*=k$ or $k+1$. Suppose that $(m^*, p^*, q^*)\ne (k,k,k)$. Then by removing all vertices outside of $B^*$ and reinserting them to internal paths in $B^*$, one can find $(m',p',q')$ such that $m'+p'+q'=3k+1$, $p'=k+1$, $m'\ne q'$ and $\rho (B(m',p',q'))<\rho (B^*)\le \rho (G)$. Without loss of generality, we may assume $m'> q'$. Since $m'+q'=2k$, we have $m'\ge k+1> k-1\ge q'$. Thus,

$$\begin{aligned} \rho (G)> \rho (B(m',p',q'))&\ge \rho (B(k+1,k+1,k-1)))&\text {(by Lemma }3.4) \\&> \rho (B(k+1,k-1,k+1))&\text {(by Lemma }3.8) \end{aligned}$$

Finally, suppose that $(m^*, p^*, q^*)=(k,k,k)$. In this case, the graph G is the graph B(k, k, k) with an extra vertex adjacent to some vertices of B(k, k, k). By Lemma 4.3, $\alpha (B(k, k, k))= \lceil \frac{n-1}{2}\rceil = \frac{n}{2}$. Since an independent set in B(k, k, k) remains independent in G, this implies $\alpha (G)\ge \frac{n}{2}$, which is a contradiction.

Therefore, we conclude that $\rho (G)\ge \rho (B(k+1,k-1,k+1))$ and we can check in the proof that the equality holds if and only if $G\cong B(k+1,k-1,k+1)$.

Case 2. $n\equiv 4\pmod {6}$

Subcase 2a. $m^*+p^*+q^*=n+1=3k-1$.

By choice of $B^*$, G should not have extra edges other than edges in $B^*$. So, we have $G=B^*=B(m^*,p^*,q^*)$ and moreover $m^*,p^*,q^*$ are all odd by Lemma 4.3.

First assume that $p^*= k-1$. Then $(m^*, q^*)\ne (k,k)$ because k is even and hence $|m^*-q^*|\ge 2$. Thus,

$$\begin{aligned} \rho (G)= \rho (B(m^*,k-1,q^*))&\ge \rho (B(k+1,k-1,k-1))&\text {(by Lemma }3.4) \\&>\rho (B(k-1,k+1,k-1))&\text {(by Lemma }3.8) \end{aligned}$$

Now assume $p^*\ne k-1$. Then we have $|\frac{m^*+q^*}{2}-p^*|\ge 2$ with equality if and only if $(m^*,p^*,q^*)=(k-1,k+1,k-1)$. So,

$$\begin{aligned} \rho (G)= \rho (B(m^*,p^*,q^*))&\ge \rho (B(\frac{m^*+q^*}{2},p^*,\frac{m^*+q^*}{2}))&\text {(by Lemma }3.4) \\&=\rho (P(\frac{m^*+q^*}{2},p^*,\frac{m^*+q^*}{2}))&\text {(by Lemma }3.2) \\&\ge \rho (P(k-1,k+1,k-1))&\text {(by Lemma }3.3) \\&= \rho (B(k-1,k+1,k-1)).&\text {(by Lemma }3.2) \end{aligned}$$

Subcase 2b. $m^*+p^*+q^*<3k-1$.

First assume that $p^*\ne k-2$ or $k-1$. Then it is not hard to see that by removing all vertices outside of $B^*$ and reinserting them to appropriately chosen internal paths in $B^*$, one can find $(m',p',q')$ such that $m'+p'+q'=3k-1$, $p'$ is odd, $p'\ne k-1$ and $\rho (B(m',p',q'))<\rho (B^*)\le \rho (G)$. Then we have $|\frac{m'+q'}{2}-p'|\ge 2$ with equality if and only if $(m',p',q')=(k-1,k+1,k-1)$. By the similar argument as above,

$$\begin{aligned}\rho (G) >\rho (B(m',p',q'))\ge \rho (B(k-1,k+1,k-1)). \end{aligned}$$

Now assume that $p^*=k-2$ or $k-1$. Suppose that $(m^*, p^*, q^*)\ne (k,k-2,k)$. Then by removing all vertices outside of $B^*$ and reinserting them to internal paths in $B^*$, one can find $(m',p',q')$ such that $m'+p'+q'=3k-1$, $p'=k-1$, $m'\ne q'$ and $\rho (B(m',p',q'))<\rho (B^*)\le \rho (G)$. Without loss of generality, we may assume $m'> q'$. Since $m'+q'=2k$, we have $m'\ge k+1> k-1\ge q'$. Thus,

$$\begin{aligned} \rho (G)> \rho (B(m',p',q'))&\ge \rho (B(k+1,k-1,k-1)))&\text {(by Lemma }3.4) \\&> \rho (B(k-1,k+1,k-1))&\text {(by Lemma }3.8) \end{aligned}$$

Finally, suppose that $(m^*, p^*, q^*)=(k,k-2,k)$. In this case, the graph G is the graph $B(k, k-2, k)$ with an extra vertex adjacent to some vertices of $B(k, k-2, k)$. By Lemma 4.3, $\alpha (B(k, k-2, k))= \lceil \frac{n-1}{2}\rceil = \frac{n}{2}$. Since an independent set in $B(k, k-2, k)$ remains independent in G, this implies $\alpha (G)\ge \frac{n}{2}$, which is a contradiction.

Therefore, we conclude that $\rho (G)\ge \rho (B(k-1,k+1,k-1))$ and we can check in the proof that the equality holds if and only if $G\cong B(k-1,k+1,k-1)$. $\square$

By Proposition 4.6, Proposition 4.7 and Proposition 4.8, the proof of Theorem 1.1 is complete.