Matching Extendability and Connectivity of Regular Graphs from Eigenvalues

Abstract

Let G be a graph on even number of vertices. A perfect matching of G is a set of independent edges which cover each vertex of G. For an integer $t\ge 1$, G is t-extendable if G has a perfect matching, and for any t independent edges, G has a perfect matching which contains these given t edges. The graph G is bi-critical if for any two vertices u and v, the graph $G-\left\{ u,v\right\}$ contains a perfect matching. Let G be a connected k-regular graph. In this paper, we obtain two sharp sufficient eigenvalue conditions for a connected k-regular graph to be 1-extendable and bi-critical, respectively. Our results are in term of the second largest eigenvalue of the adjacency matrix of G. We also give examples that show that there is no good spectral characterization (in term of the second largest eigenvalue of the adjacency matrix) for 2-extendability of regular graphs in general. Also, for any integer $1\le \ell <\frac{k+2}{2}$, we obtain an eigenvalue condition for G to be $(\ell +1)$-connected.

1 Introduction

All graphs considered are finite, undirected and simple in this paper. Let G be a graph. The vertex set and the edge set of G are denoted by V(G) and E(G) respectively. Let B and E be a subset of V(G) and a subset of E(G) respectively. The graph $G-B$ is derived from G by deleting the vertices of B and the edges incident with a vertex of B. If $B=\left\{ u\right\}$, we denote $G-B$ by $G-u$ for convenience. The graph G[B] is the subgraph induced by B. We also denote G[B] by B if no ambiguity arises. The graph $G-E$ is defined with vertex set $V(G-E)=V(G)$ and edge set $E(G)-E$. Let S and T be two non-empty disjoint subsets of V(G) (or subgraphs of G). Define E(S, T) to be the set of edges of which one end vertex is in S and the other end vertex is in T. The connectivity of a connected graph G is the minimum size of a subset S of V(G) such that $G-S$ is disconnected or singleton. If the connectivity of G is not less than $\ell$, we say that G is $\ell$-connected.

A matchingM of G is a set of independent edges of G. If M covers each vertex of G, then M is called a perfect matching or a one-factor. Theorem 2.1 is a fundamental result in matching theory [1, 16]. Let G be a graph on even number of vertices. For an integer $t\ge 1$, if G has a perfect matching, and for any t independent edges of G, G has a perfect matching which contains these given t edges, then G is called t-extendable. If for any two vertices x and y of G the graph $G-\left\{ x,y\right\}$ has a perfect matching, then G is called bi-critical. For more studies of bi-critical graphs, one may refer to [13, 14]. Matching plays an important role in graph theory and is widely applied in economics and chemistry. In the book [12], There is an extensive research on matching in combination. In the papers [2, 5], the authors studied matchings of regular graphs by interlacing technique (see Theorem 2.2). For matching extensions of strongly regular graphs and distance-regular graphs, one may refer to [7, 11] and [6] respectively. There is a conjecture in [7] that primitive strongly regular graphs of valency k have extendability at least $k/2-1$. It is still open.

Let G be a graph with vertices $1,2,\ldots ,n=|V(G)|$. The adjacency matrixA of G is a square matrix indexed by the vertices of G, where $a_{ij}=1$ if the vertex i and the vertex j are adjacent in graph G, and $a_{ij}=0$ otherwise. The eigenvalues of G are the eigenvalues of its adjacency matrix A. In the current paper, we always denote the eigenvalues of a graph G by $\lambda _{1}(G)\ge \lambda _{2}(G)\ge \cdots \ge \lambda _{n}(G)$. As well known, $\lambda _{1}(G)$ is the spectral radius of G and its multiplicity is one if the graph G is connected by Perron-Frobenius Theorem. For a (vertex) partition $V_{1},V_{2},...V_{m}$ of V(G), the corresponding quotient matrix of the partition is an $m\times m$ matrix and the element in (i, j) is $\frac{\Sigma _{ij}}{|V_{i}|}$, where $\Sigma _{ij}=|E(V_{i},V_{j})|$ for any $i\ne j$, and $\Sigma _{ii}=2|E(G[V_{i}])|$ for $1\le i\le m$. The partition is equitable if each vertex in $V_{i}$ has the same number of neighbors in $V_{j}$ for any $i\ne j$, and $G[V_{i}]$ is regular for any $1\le i\le m$.

For a graph G on n vertices, let $s_{k}$ denote the sum of k largest eigenvalues of G, where $k\ge 2$. It showed that $s_{2}\le \left( \frac{1}{2}+\sqrt{\frac{5}{12}}\right) n$ in [8] and $s_{k}\le \frac{1}{2}\left( \sqrt{k}+1\right) n$ in [15], respectively. For a connected k-regular graph G on even number of vertices, in [2] the authors obtained a sufficient eigenvalue condition for G to have a perfect matching, and constructed a k-regular graph $H_{k}$ on even number of vertices with no perfect matchings, which shows that the condition is tight. Later, in [5] the authors showed that G has a perfect matching if $\lambda _{3}(G)<\lambda _{3}(H_{k})$.

In this paper, we consider a connected regular graph G of degree $k\ge 3$. We first construct a k-regular graph $H_{k}$ which is not 1-extendable, and a k-regular graph $N_{k}$ which is not bi-critical, respectively. Then we show that G is 1-extendable when $\lambda _{2}(G)<\lambda _{2}(H_{k})$, and G is bi-critical when G is non-bipartite and $\lambda _{2}(G)<\lambda _{2}(N_{k})$. In Theorem 2.5, we also obtain a sufficient eigenvalue condition involving the number of vertices of G for G to be 1-extendable. Our proofs are mainly based on Theorem 2.1 (Tutte Theorem) and Theorem 2.2 (Interlacing Technique). In the Remark 2.5, we also give examples that show that there is no good spectral characterization (in term of the second largest eigenvalue of the adjacency matrix) for 2-extendability of regular graphs in general. For any integer $1\le \ell <\frac{k+2}{2}$, we show that G is $(\ell +1)$-connected if $\lambda _{2}(G)\le k-\frac{\ell }{2}\frac{k}{k-\ell +1}$. For any terminology used but not defined here, one may refer to [3, 12].

2 1-Extendable Regular Graphs from Eigenvalues

Let S be a subset of V(G). The number of odd components of $G-S$ is denoted by $o(G-S)$. Tutte [16] (or [1]) proved the following fundamental result in matching theory.

Theorem 2.1

(Tutte Theorem) A graph G contains a perfect matching if and only if $o(G-S)\le |S|$ for any subset S of V(G).

The following Theorem 2.2 is the generalized form of (eigenvalue) interlacing technique, referring to [3] (Chapter 2 and Chapter 3) or [10]. For more studies of interlacing technique, one may refer to [2, 4, 5].

Theorem 2.2

(Interlacing Technique) Let G be a graph of order n and Q be the $m\times m$ quotient matrix of G for a partition $V_{1},V_{2},...V_{m}$. Then we have the followings.

• (i) The eigenvalues of Q interlace those of G. In other words, $\lambda _{i}(G)\ge \lambda _{i}(Q)\ge \lambda _{i+n-m}(G)$ for any $1\le i\le m$.

• (ii) If the partition is equitable, then each eigenvalue (with multiplicity) of Q is also an eigenvalue of G.

• (iii) If the interlacing is tight, which means that there is an integer $h\ge 0$ such that $\lambda _{i}(Q)=\lambda _{i}(G)$ for $1\le i\le h$ and $\lambda _{i}(Q)=\lambda _{i+n-m}(G)$ for $h+1\le i\le m$, then the partition is equitable.

It is worth mentioning that when Q is a principle submatrix of the adjacency matrix of G, the conclusion (i) of Theorem 2.2 is also satisfied. This is the original form of (eigenvalue) interlacing technique. In the followings, when we say Theorem 2.2, we admit that the original form is involved.

Let $K_{n}$ and $C_{n}$ denote a complete graph and a cycle on n vertices respectively. If n is an even integer, let $M_{n}$ denote a perfect matching on n vertices. For a graph H, let $\overline{H}$ be the complement of H. For two (vertex) disjoint graphs $G_{1}$ and $G_{2}$, the joint of $G_{1}$ and $G_{2}$, which is denoted by $G_{1}+G_{2}$, is the graph formed by adding an edge between each vertex of $G_{1}$ and each vertex of $G_{2}$.

For an even integer $k\ge 4$, let $A=K_{2}$, $B=\overline{K_{k-2}}$ (a set of $k-2$ isolated vertices), $C=\overline{K_{k-1}}$ and $D=K_{3}+\overline{M_{k-2}}$, respectively. Define a new graph $H_{k}$ with the four parts A, B, C and D by adding an edge from each vertex in $A\bigcup B$ to each vertex in C, and also adding a perfect matching between the vertices in B and the vertices of degree $k-1$ in D. Thus $H_{k}$ is a k-regular graph on 3k vertices.

For an odd integer $k\ge 5$, let $A=K_{2}$, $B=\overline{K_{k-2}}$, $C=\overline{K_{k-1}}$ and $D=C_{4}+\overline{C_{k-2}}$, respectively. Define a new graph $H_{k}$ with the four parts A, B, C and D by adding an edge from each vertex in $A\bigcup B$ to each vertex in C, and also adding a perfect matching between the vertices in B and the vertices of degree $k-1$ in D. Thus $H_{k}$ is a k-regular graph on $3k+1$ vertices.

Theorem 2.3

Let $H_{k}$ be the graph defined above for $k\ge 4$. Then $H_{k}$ is not 1-extendable and we also have the followings.

• (i) If $k\ge 4$ is an even integer, then $\lambda _{2}(H_{k})$ is the largest root of polynomial $f_{k}(\lambda )=\lambda ^{4}+\lambda ^{3}-(k^{2}-2k+5)\lambda ^{2}-(5k-7)\lambda +k^{2}-k$. Moreover, we have $k-\frac{3}{2}+\frac{33}{8k}<\lambda _{2}(H_{k})<k-\frac{3}{2}+\frac{33}{8k}+\frac{27}{8k(k-4)}$ for $k\ge 8$, $\sqrt{12}<\lambda _{2}(H_{4})<\sqrt{13}$ and $\sqrt{27}<\lambda _{2}(H_{6})<\sqrt{28}$.

• (ii) If $k\ge 5$ is an odd integer, then $\lambda _{2}(H_{k})$ is the largest root of polynomial $f_{k}(\lambda )=\lambda ^{4}+2\lambda ^{3}-(k^{2}-2k+6)\lambda ^{2}-(k^{2}+4k-7)\lambda +2k^{2}-4k+2$. Moreover, we have $k-\frac{3}{2}+\frac{39}{8k}<\lambda _{2}(H_{k})<k-\frac{3}{2}+\frac{41}{8k}-\frac{3}{8k(k-3)}$ for $k\ge 11$, $\sqrt{19}<\lambda _{2}(H_{5})<\sqrt{20}$, $\sqrt{38}<\lambda _{2}(H_{7})<\sqrt{39}$ and $\sqrt{64}<\lambda _{2}(H_{9})<\sqrt{65}$.

Proof

For $k\ge 4$, the part A is an edge and it is easy to see that $H_{k}-A$ has no perfect matching by Theorem 2.1 as $o(H_{k}-A-B)=k>|B|=k-2$. Thus $H_{k}$ is not 1-extendable.

(i) Let $k\ge 4$ be an even integer. Partition $V(H_{k})$ into five parts $V_{1}=A,V_{2}=B,V_{3}=C,V_{4}=\overline{M_{k-2}}$ and $V_{5}=K_{3}$ (Notice that $D=K_{3}+\overline{M_{k-2}}$), respectively. It is easy to see that this partition is equitable. Thus the eigenvalues of the quotient matrix B corresponding to the partition are also the eigenvalues of $H_{k}$ by Theorem 2.2. It is easy to see that B is equal to

$$\begin{aligned} \left( \begin{array}{ccccc} 1&{}\quad 0&{}\quad k-1&{}\quad 0&{}\quad 0\\ 0&{}\quad 0&{}\quad k-1&{}\quad 1&{}\quad 0\\ 2&{}\quad k-2&{}\quad 0&{}\quad 0&{}\quad 0\\ 0&{}\quad 1&{}\quad 0&{}\quad k-4&{}\quad 3\\ 0&{}\quad 0&{}\quad 0&{}\quad k-2&{}\quad 2 \end{array}\right) . \end{aligned}$$

By a routine computing, the characteristic polynomial of B is $(\lambda -k)f_{k}(\lambda )$. Let $p_{k}$ be the largest root of $f_{k}(\lambda )$. For $k\ge 8$, set $\lambda =k-\frac{3}{2}+\frac{y}{k}$, where $0\le y<\frac{3k}{2}$. Then we have $f_{k}(\lambda )=\left( 2y-\frac{33}{4}\right) k^{2} +\left( \frac{105}{4}-8y\right) k+\left( 5y^{2}-3y-\frac{321}{16}\right) +\frac{-13y^{2}+\frac{61}{4}y}{k}+\frac{4y^{3}+4y^{2}}{k^{2}} -\frac{5y^{3}}{k^{3}}+\frac{y^{4}}{k^{4}}$$(*)$ by a routine computing. The sum of first two terms of $(*)$ is nonnegative for $y\ge \frac{33}{8}+\frac{27}{8(k-4)}$. Also, the sum of the following two terms $\left( 5y^{2}-3y-\frac{321}{16}\right) +\frac{-13y^{2}+\frac{61}{4}y}{k}$ of $(*)$ is positive for $y\ge 4$ and the sum of the last three terms of $(*)$ is positive for $y>0$. Therefore, $f_{k}\left( k-\frac{3}{2}+\frac{y}{k}\right) >0$ for $y\ge \frac{33}{8}+\frac{27}{8(k-4)}$, which implies $p_{k}<k-\frac{3}{2}+\frac{33}{8k}+\frac{27}{8k(k-4)}$ for $k\ge 8$. Similarly, it can be checked that $f_{k}\left( k-\frac{3}{2}+\frac{33}{8k}\right) <0$ by letting $y=\frac{33}{8}$ in $(*)$, which implies $p_{k}>k-\frac{3}{2}+\frac{33}{8k}$ for $k\ge 8$.

It is easy to see that $\sqrt{12}<\lambda _{2}(H_{4})<\sqrt{13}$ and $\sqrt{27}<\lambda _{2}(H_{6})<\sqrt{28}$ by computation.

As well known, each eigenvector corresponding to the eigenvalue of B can be lifted to be an eigenvector of $H_{k}$ corresponding to the same eigenvalue, such that the components (of each lifted eigenvector of $H_{k}$) in each part of the equitable partition are the same (see [10]). Let W be the space spanned by the five characteristic vectors of the five parts $V_{1},V_{2},\ldots ,V_{5}$. (Here, for a subset A of the vertex set of a graph G, the characteristic vector of A is a vector ${\mathbf {x}}$ indexed by V(G), such that the component $x_{u}=1$ if the vertex u is in A, and the component $x_{u}=0$ otherwise.) Obviously, the space W has dimension 5. Since the five lifted eigenvectors of $H_{k}$ corresponding to the five eigenvectors of B are linear independent and in W, thus these five lifted eigenvectors also span the space W. Therefore, any other eigenvalue of $H_{k}$ with an eigenvector orthogonal to W is also an eigenvalue of the graph $H_{k}^{'}$ derived from $H_{k}$ by deleting all the edges between any two distinct parts (of the five parts) when each vertex of one part is adjacent to each vertex of the other part in $H_{k}$. Since the maximal degree in the graph $H_{k}^{'}$ is at most $k-3$, which is less than $p_{k}$, thus $p_{k}$ is the second largest eigenvalue of $H_{k}$.

(ii) Let $k\ge 5$ be an odd integer. Partition $V(H_{k})$ into five parts $V_{1}=A,V_{2}=B,V_{3}=C,V_{4}=\overline{C_{k-2}}$ and $V_{5}=C_{4}$ (Notice that $D=C_{4}+\overline{C_{k-2}}$), respectively. It is easy to see that this partition is equitable. Thus the eigenvalues of the quotient matrix B corresponding to the partition are also the eigenvalues of $H_{k}$ by Theorem 2.2. It is easy to see that B is equal to

$$\begin{aligned} \left( \begin{array}{ccccc} 1&{}\quad 0&{}\quad k-1&{}\quad 0&{}\quad 0\\ 0&{}\quad 0&{}\quad k-1&{}\quad 1&{}\quad 0\\ 2&{}\quad k-2&{}\quad 0&{}\quad 0&{}\quad 0\\ 0&{}\quad 1&{}\quad 0&{}\quad k-5&{}\quad 4\\ 0&{}\quad 0&{}\quad 0&{}\quad k-2&{}\quad 2 \end{array}\right) . \end{aligned}$$

By a routine computing, the characteristic polynomial of B is $(\lambda -k)f_{k}(\lambda )$. Let $p_{k}$ be the largest root of $f_{k}(\lambda )$. For $k\ge 11$, set $\lambda =k-\frac{3}{2}+\frac{y}{k}$, where $0\le y<\frac{3k}{2}$. Then we have $f_{k}(\lambda )=\left( 2y-\frac{41}{4}\right) k^{2}+\left( \frac{63}{2}-6y\right) k +\left( 5y^{2}-13y-\frac{379}{16}\right) +\frac{-10y^{2}+25y}{k}+\frac{4y^{3} -\frac{3}{2}y^{2}}{k^{2}}-\frac{4y^{3}}{k^{3}}+\frac{y^{4}}{k^{4}}$$(**)$ by a routine computing. For $y\ge \frac{41}{8}-\frac{3}{8(k-3)}$, it is easy to check that not only the sum of first two terms of $(**)$ is nonnegative, but also the sum of the following two terms of $(**)$ is nonnegative. Also, the sum of the last three terms of $(**)$ is positive for $y\ge 1$. Therefore, $f_{k}\left( k-\frac{3}{2}+\frac{y}{k}\right) >0$ for $y\ge \frac{41}{8}-\frac{3}{8(k-3)}$, which implies $p_{k}<k-\frac{3}{2}+\frac{41}{8k}-\frac{3}{8k(k-3)}$ for $k\ge 11$. Similarly, it can be checked that $f_{k}\left( k-\frac{3}{2}+\frac{39}{8k}\right) <0$ by letting $y=\frac{39}{8}$ in $(**)$, which implies $p_{k}>k-\frac{3}{2}+\frac{39}{8k}$ for $k\ge 11$.

It is easy to see that $\sqrt{19}<\lambda _{2}(H_{5})<\sqrt{20}$, $\sqrt{38}<\lambda _{2}(H_{7})<\sqrt{39}$ and $\sqrt{64}<\lambda _{2}(H_{9})<\sqrt{65}$ by computation.

Similar to the proof of case (i), we can show that $p_{k}$ is the second largest eigenvalue of $H_{k}$, where $k\ge 5$ is an odd integer. We complete the proof. $\square$

Theorem 2.4

Let G be a connected regular graph of degree $k\ge 19$ on even number n of vertices. If $\lambda _{2}(G)<\lambda _{2}(H_{k})$, then G is 1-extendable.

Proof

Let R be an odd subset of V(G). By $|E(R,\overline{R})|+2|E(G[R])|=k|R|$ we have that $|E(R,\overline{R})|$ has the same parity with k, where $\overline{R}=V(G)-R$. If P is a subset of V(G) with $|P|\le k$, then $|E(P,\overline{P})|\ge (k-|P|+1)|P|\ge k$. (We will use these two facts many times in the following proof.)

We prove the conclusion by contradiction. Assume that G is not 1-extendable. Then there is an edge $e=xy$ of G such that $G-x-y$ has no perfect matching. By Theorem 2.1, there is a subset $S_{0}$ of $V(G-x-y)$ such that $o(G-x-y-S_{0})>|S_{0}|$, and thus $o(G-x-y-S_{0})\ge |S_{0}|+2$ by parity. Let $S=S_{0}\bigcup \left\{ x,y\right\}$. Then G[S] contains an edge and $o(G-S)\ge |S|$. We choose the maximal S such that G[S] contains an edge and $o(G-S)\ge |S|$. By the choice of S, there is no even component in $G-S$. If $o(G-S)>|S|$ and thus $o(G-S)\ge |S|+2$ by parity, then there exist two odd components, say P and Q, such that $|E(P,S)|\le k-2, |E(Q,S)|\le k-2$ and thus $|P|,|Q|\ge k+1$ by regularity and parity. By Theorem 2.2, we have $\lambda _{2}(G)\ge min\left\{ \lambda _{1}(P),\lambda _{1}(Q)\right\} \ge k-\frac{k-2}{k+1}>\lambda _{2}(H_{k})$ for $k\ge 19$, a contradiction. Therefore, we have $o(G-S)=|S|$.

(i) Suppose that $k\ge 19$ is an odd integer. There exists an odd component of $G-S$, say $P_{1}$, such that $|E(P_{1},S)|<k$ by regularity, since G[S] contains an edge. It follows that $|E(P_{1},S)|\le k-2$ and thus $|P_{1}|\ge k+2$ by parity (see the first paragraph of this proof).

Suppose that there are at least two odd components of $G-S$ which are not singleton components. Then there exist two non-singleton components, say P and Q, such that $|E(P,S)|\le |E(Q,S)|$ and $|E(P,S)|+|E(Q,S)|\le 2k-2$ by regularity as G[S] contains an edge. It is easy to see that $|E(P,S)|\le k-2$ and thus $|P|\ge k+2$. If $|Q|\le k-2$, then $|E(Q,S)|\ge (k+1-|Q|)|Q|\ge 3k-6\ge 2k-2$, which is impossible. It implies $|Q|\ge k$. Set $|E(P,S)|=a\le k-2$. By Theorem 2.2, we have $\lambda _{2}(G)\ge min\left\{ \lambda _{1}(P),\lambda _{1}(Q)\right\} \ge min\left\{ k-\frac{a}{k+2},k-\frac{2k-2-a}{k}\right\} = k-\frac{2k-2-a}{k}$. Partition V(G) into two parts P and $\overline{P}$, respectively. The quotient matrix of this partition is easy to compute, and by Theorem 2.2 we have $\lambda _{2}(G)\ge k-\frac{a}{k+2}-\frac{a}{k+2}$ as $|P|,|\overline{P}|\ge k+2$. Therefore, we have $\lambda _{2}(G)\ge max\left\{ k-\frac{2k-2-a}{k}, k-\frac{a}{k+2}-\frac{a}{k+2}\right\} \ge k-\frac{4k^{2}+4k-8}{3k^{2}+8k+4}$$\left( \mathrm{when}\; a=\frac{2k^{2}+2k-4}{3k+2}\right)$. By a routine computing, $k-\frac{4k^{2}+4k-8}{3k^{2}+8k+4}\ge k-\frac{3}{2}+\frac{41}{8k}-\frac{3}{8k(k-3)}$ if and only if $4k^{4}-67k^{3}-42k^{2}+508k+504\ge 0$. It is satisfied for $k\ge 17$ and thus $\lambda _{2}(G)>\lambda _{2}(H_{k})$ for $k\ge 19$, a contradiction.

Now we can suppose that there is precisely one non-singleton odd component, say P. Thus $o(G-S)=|S|\ge k$ and $n\ge 3k+1$, since $|E(P,S)|<k$ and thus $|P|\ge k+2$. Set $|E(P,S)|=a$. If $a<k-2$ and thus $a\le k-4$ by parity, partition V(G) into two parts P and $\overline{P}$, respectively. By Theorem 2.2 we have $\lambda _{2}(G)\ge k-\frac{a}{|P|}-\frac{a}{n-|P|}\ge k-\frac{k-4}{k+2}-\frac{k-4}{2k-1}$ as $|P|\ge k+2, n-|P|\ge k+2$ and $n\ge 3k+1$. By a routine computing, $k-\frac{k-4}{k+2}-\frac{k-4}{2k-1}\ge k-\frac{3}{2}+\frac{41}{8k}-\frac{3}{8k(k-3)}$ if and only if $42k^{3}-235k^{2}+436k-252\ge 0$. It is satisfied for $k\ge 7$ and thus $\lambda _{2}(G)>\lambda _{2}(H_{k})$ for $k\ge 19$, a contradiction. Now let $|E(P,S)|=a=k-2$.

If $n=3k+1$, then $|P|=k+2$ and $|S|=k$. Since $|E(P,S)|=k-2$, thus there exist four vertices $u_{1},u_{2},u_{3}$ and $u_{4}$ of degree k in G[P]. Set $V_{5}^{'}=\left\{ u_{1},u_{2},u_{3},u_{4}\right\}$ (compared with $V_{5}$ in $H_{k}$). Let $V_{1}^{'}$ be the two ends of the only edge in S, $V_{2}^{'}=S-V_{1}^{'}$, $V_{3}^{'}=V(G)-P-S$ and $V_{4}^{'}=P-V_{5}^{'}$, respectively. Thus G has a partition which contains five parts (compared with $H_{k}$). It is easy to see that $|E(G[V_{5}^{'}])|=4+\varepsilon$, where $\varepsilon =0,1$ or 2. The quotient matrix C of this partition of G is equal to

$$\begin{aligned} \left( \begin{array}{ccccc} 1&{}\quad 0&{}\quad k-1&{}\quad 0&{}\quad 0\\ 0&{}\quad 0&{}\quad k-1&{}\quad 1&{}\quad 0\\ 2&{}\quad k-2&{}\quad 0&{}\quad 0&{}\quad 0\\ 0&{}\quad 1&{}\quad 0&{}\quad k-5+\frac{2\varepsilon }{k-2}&{}\quad 4-\frac{2\varepsilon }{k-2}\\ 0&{}\quad 0&{}\quad 0&{}\quad k-2-\frac{\varepsilon }{2}&{}\quad 2+\frac{\varepsilon }{2} \end{array}\right) . \end{aligned}$$

Let the characteristic polynomial of matrix C be $(\lambda -k)g(\lambda )$. By adding the first four columns to the last column, we have $g(\lambda )-f_{k}(\lambda )=\frac{-\varepsilon }{2(k-2)}h(\lambda )$, where $h(\lambda )=(k+2)\lambda ^{3}-4\lambda ^{2}-(k^{3}+2k-4)\lambda +k^{3}-2k^{2}-k+2$. By a routine computing, we have $((k+2)\lambda +2k+8)h(\lambda )-(k+2)^{2}f_{k}(\lambda )=F(\lambda )$, where $F(\lambda )=8k\lambda ^{2}+(4k^{2}-20k+8)\lambda -12k^{2}+4k+8$. Since $\lambda _{2}(H_{k})>4$ for $k\ge 5$, thus $F(\lambda _{2}(H_{k}))>4k^{2}+52k+40>0$, which implies $h(\lambda _{2}(H_{k}))>0$ and thus $g(\lambda _{2}(H_{k}))\le 0$ for $k\ge 5$. By Theorem 2.2, we have $\lambda _{2}(G)\ge \lambda _{2}(H_{k})$ for $k\ge 19$, a contradiction.

Suppose $n= 3k+3$. If $|S|=k$, then $|P|=k+4$. Partition V(G) into two parts P and $\overline{P}$, respectively. By Theorem 2.2, $\lambda _{2}(G)\ge k-\frac{k-2}{|P|}-\frac{k-2}{n-|P|}\ge k-\frac{k-2}{k+4}-\frac{k-2}{2k-1}$ as $|P|\ge k+4, n-|P|\ge k+4$ and $n=3k+3$. By a routine computing, $k-\frac{k-2}{k+4}-\frac{k-2}{2k-1}\ge k-\frac{3}{2}+\frac{41}{8k}-\frac{3}{8k(k-3)}$ if and only if $26k^{3}-359k^{2}+1046k-504\ge 0$. It is satisfied for $k\ge 11$ and thus $\lambda _{2}(G)>\lambda _{2}(H_{k})$ for $k\ge 19$, a contradiction. If $|S|=k+1$, then $|P|=k+2$. Partition V(G) into three parts P, S and $V(G)-P-S$, respectively. The quotient matrix of this partition is easy to compute, and by Theorem 2.2 and a routine computing, we have $\lambda _{2}(G)\ge \frac{\sqrt{4k^{6}+16k^{5}+29k^{4}+26k^{3}+13k^{2}+36k+36}-k^{2}+3k+6}{2(k+1)(k+2)}$. Since $\sqrt{4k^{6}+16k^{5}+29k^{4}+26k^{3}+13k^{2}+36k+36}\ge 2k^{3}+4k^{2}+\frac{13}{4}k$ for $k\ge 0$ by a routine computing, thus $\lambda _{2}(G)\ge \frac{2k^{3}+3k^{2}+\frac{25}{4}k+6}{2(k+1)(k+2)}\ge k-\frac{3}{2}+\frac{41}{8k}-\frac{3}{8k(k-3)}$ whenever $k^{3}-21k^{2}+38k+63\ge 0$. It is satisfied when $k\ge 19$, which implies $\lambda _{2}(G)>\lambda _{2}(H_{k})$ for $k\ge 19$, a contradiction.

Suppose $n\ge 3k+5$. Partition V(G) into two parts P and $\overline{P}$, respectively. By Theorem 2.2 we have $\lambda _{2}(G)\ge k-\frac{k-2}{|P|}-\frac{k-2}{n-|P|}\ge k-\frac{k-2}{k+2}-\frac{k-2}{2k+3}$ as $|P|\ge k+2, n-|P|\ge k+2$ and $n\ge 3k+5$. By a routine computing, $k-\frac{k-2}{k+2}-\frac{k-2}{2k+3}\ge k-\frac{3}{2}+\frac{41}{8k}-\frac{3}{8k(k-3)}$ if and only if $10k^{3}-159k^{2}+180k+756\ge 0$. It is satisfied for $k\ge 15$ and thus $\lambda _{2}(G)>\lambda _{2}(H_{k})$ for $k\ge 19$, a contradiction. Now we complete the proof of case (i).

(ii) Suppose that $k\ge 20$ is an even integer. There exists an odd component of $G-S$, say $P_{1}$, such that $|E(P_{1},S)|<k$. It follows that $|E(P_{1},S)|\le k-2$ by parity and thus $|P_{1}|\ge k+1$.

If there exist at least two odd components of $G-S$ which are not singleton components, then we can choose two non-singleton odd components, say P and Q, such that $|E(P,S)|\le |E(Q,S)|$ and $|E(P,S)|+|E(Q,S)|\le 2k-2$ by regularity as G[S] contains an edge. It is easy to see that $|E(P,S)|\le k-2$ and thus $|P|\ge k+1$. If $|Q|\le k-1$, then $|E(Q,S)|\ge (k+1-|Q|)|Q|\ge 2k-2$, which is impossible. It implies $|Q|\ge k+1$. Set $|E(P,S)|=a\le k-2$. By Theorem 2.2, we have $\lambda _{2}(G)\ge min\left\{ \lambda _{1}(P),\lambda _{1}(Q)\right\} \ge min\left\{ k-\frac{a}{k+1},k-\frac{2k-2-a}{k+1}\right\} = k-\frac{2k-2-a}{k+1}$. Partition V(G) into two parts P and $\overline{P}$, respectively. By Theorem 2.2 we have $\lambda _{2}(G)\ge k-\frac{a}{k+1}-\frac{a}{k+3}$ as $|P|\ge k+1, |\overline{P}|\ge k+3$. Therefore, $\lambda _{2}(G)\ge max\left\{ k-\frac{2k-2-a}{k+1},k-\frac{a}{k+1}-\frac{a}{k+3}\right\} \ge k-\frac{4k^{2}+4k-8}{3k^{2}+10k+7}$$\left( \mathrm{when}\; a=\frac{2k^{2}+4k-6}{3k+7}\right)$. By a routine computing, $k-\frac{4k^{2}+4k-8}{3k^{2}+10k+7}\ge k-\frac{3}{2}+\frac{33}{8k}+\frac{27}{8k(k-4)}$ if and only if $4k^{4}-27k^{3}-347k^{2}+739k+735\ge 0$. It is satisfied for $k\ge 14$, and thus $\lambda _{2}(G)>\lambda _{2}(H_{k})$ for $k\ge 20$, which is contradictive to the hypothesis.

Now we can suppose that there is precisely one non-singleton odd component, say P. Thus $o(G-S)=|S|\ge k$ and $n\ge 3k$, since $|E(P,S)|<k$ and thus $|P|\ge k+1$. Set $|E(P,S)|=a$. If $a<k-2$, then $a\le k-4$ as a has the same parity with k. Partition V(G) into two parts P and $\overline{P}$, respectively. By Theorem 2.2 we have $\lambda _{2}(G)\ge k-\frac{a}{|P|}-\frac{a}{n-|P|}\ge k-\frac{k-4}{k+1}-\frac{k-4}{2k-1}$ as $|P|\ge k+1, n-|P|\ge k+1$ and $n\ge 3k$. By a routine computing, $k-\frac{k-4}{k+1}-\frac{k-4}{2k-1}\ge k-\frac{3}{2}+\frac{33}{8k}+\frac{27}{8k(k-4)}$ if and only if $42k^{3}-267k^{2}+186k-105\ge 0$. It is satisfied for $k\ge 6$, and thus $\lambda _{2}(G)>\lambda _{2}(H_{k})$ for $k\ge 20$, a contradiction. Now we can suppose $|E(P,S)|=a=k-2$.

If $n=3k$, then $|P|=k+1$ and $|S|=k$. Let $V_{5}^{'}$ be the set of any three vertices of degree k in G[P] (compared with the set $V_{5}=K_{3}$ in the partition of $H_{k}$), $V_{1}^{'}$ be the two ends of the only edge in S, $V_{2}^{'}=S-V_{1}^{'}$, $V_{3}^{'}=V(G)-P-S$ and $V_{4}^{'}=P-V_{5}^{'}$, respectively. Thus G has a partition which contains five parts (compared with $H_{k}$). It is easy to see that the quotient matrices of G and $H_{k}$ are the same. By Theorem 2.2, we have $\lambda _{2}(G)\ge \lambda _{2}(H_{k})$, a contradiction.

Suppose $n=3k+2$. If $|S|=k$, then $|P|=k+3$. Partition V(G) into two parts P and $\overline{P}$, respectively. By Theorem 2.2 we have $\lambda _{2}(G)\ge k-\frac{k-2}{|P|}-\frac{k-2}{n-|P|}\ge k-\frac{k-2}{k+3}-\frac{k-2}{2k-1}$ as $|P|\ge k+3, n-|P|\ge k+3$ and $n= 3k+2$. By a routine computing, $k-\frac{k-2}{k+3}-\frac{k-2}{2k-1}\ge k-\frac{3}{2}+\frac{33}{8k}+\frac{27}{8k(k-4)}$ if and only if $26k^{3}-291k^{2}+496k-315\ge 0$. It is satisfied for $k\ge 10$, and thus $\lambda _{2}(G)>\lambda _{2}(H_{k})$ for $k\ge 20$, a contradiction. If $|S|=k+1$, then $|P|=k+1$. Partition V(G) into three parts P, S and $V(G)-P-S$, respectively. The quotient matrix of this partition is easy to compute, and by Theorem 2.2 we have $\lambda _{2}(G)\ge \frac{\sqrt{4k^{4}+9k^{2}-8k+16}-k+4}{2k+2}$. Since $\sqrt{4k^{4}+9k^{2}-8k+16}\ge 2k^{2}+\frac{9}{4}-\frac{2}{k}$ for $k\ge 1$ by a routine computing, thus $\lambda _{2}(G)\ge \frac{2k^{2}+\frac{9}{4}-\frac{2}{k}-k+4}{2k+2}\ge k-\frac{3}{2}+\frac{33}{8k}+\frac{27}{8k(k-4)}$ whenever $4k^{2}-84k+137\ge 0$. It is satisfied for $k\ge 20$, which implies $\lambda _{2}(G)>\lambda _{2}(H_{k})$ for $k\ge 20$, a contradiction.

Suppose $n\ge 3k+4$. Partition V(G) into two parts P and $\overline{P}$, respectively. By Theorem 2.2 we have $\lambda _{2}(G)\ge k-\frac{k-2}{|P|}-\frac{k-2}{n-|P|}\ge k-\frac{k-2}{k+1}-\frac{k-2}{2k+3}$ as $|P|\ge k+1, n-|P|\ge k+1$ and $n\ge 3k+4$. By a routine computing, $k-\frac{k-2}{k+1}-\frac{k-2}{2k+3}\ge k-\frac{3}{2}+\frac{33}{8k}+\frac{27}{8k(k-4)}$ if and only if $10k^{3}-159k^{2}+26k+315\ge 0$. It is satisfied for $k\ge 16$, and thus $\lambda _{2}(G)>\lambda _{2}(H_{k})$ for $k\ge 20$, a contradiction. We complete the proof. $\square$

Remark 2.1

Let $G_{k}=\overline{K_{k-2}}+C_{k}$, where $k\ge 4$. It is not difficult to show that the spectrum of $G_{k}$ is $k,2-k,0^{k-3},2\cos \frac{2\pi }{k},2\cos \frac{4\pi }{k}, \ldots ,2\cos \frac{2(k-1)\pi }{k}$. It implies $\lambda _{2}(G_{k})=2\cos \frac{2\pi }{k}$. But $G_{k}$ is not 2-extendable, since any two independent edges in the part $C_{k}$ of $G_{k}$ are not contained in a perfect matching of $G_{k}$. Thus there is no good spectral characterization (in term of the second largest eigenvalue of the adjacency matrix) like Theorem 2.4 for 2-extendability of regular graphs in general.

Theorem 2.5

Let G be a connected regular graph of degree $k\ge 3$ on even number n of vertices. Then we have the following conclusions.

• (i) For odd integer $k\ge 3$, if $n\le 2k+2$, then G is 1-extendable; if $2k+4\le n\le 3k-1$ and $\lambda _{2}(G)\le k-1+\frac{3}{2k+1}$, then G is 1-extendable; if $n\ge 3k+1$ and $\lambda _{2}(G)\le min\left\{ k-1+\frac{3}{2k+1},k-1+\frac{4}{k+2}-\frac{k-1}{8(k-1)^{2}-1} -\frac{k-2}{n-k-1}\right\}$, then G is 1-extendable.

• (ii) For even integer $k\ge 4$, if $n\le 2k+2$, then G is 1-extendable; if $2k+4\le n\le 3k-2$ and $\lambda _{2}(G)\le k-1+\frac{2}{k+1}$, then G is 1-extendable; if $n\ge 3k$ and $\lambda _{2}(G)\le min\left\{ k-1+\frac{2}{k+1},k-1 +\frac{3}{k+1}-\frac{k-1}{8(k-1)^{2}-1}-\frac{k-2}{n-k}\right\}$, then G is 1-extendable.

Proof

We prove the conclusion by contradiction. Assume that G is not 1-extendable. Similar to Theorem 2.4, by Theorem 2.1 there is a subset S of V(G) such that G[S] contains an edge and $o(G-S)\ge |S|$. We choose the maximal S such that G[S] contains an edge and $o(G-S)\ge |S|$. By the choice of S, there is no even component in $G-S$.

(i) Suppose that $k\ge 3$ is an odd integer. There exists an odd component of $G-S$, say $P_{1}$, such that $|E(P_{1},S)|<k$ by regularity, since G[S] contains an edge. It follows that $|E(P_{1},S)|\le k-2$ and thus $|P_{1}|\ge k+2$ by parity. Therefore, we have $n\ge 2k+4$, since $|\overline{P_{1}}|\ge k+2$.

Suppose that there are at least two odd components of $G-S$ which are not singleton components. Then there exist two non-singleton components, say P and Q, such that $|E(P,S)|\le |E(Q,S)|$ and $|E(P,S)|+|E(Q,S)|\le 2k-2$ by regularity as G[S] contains an edge. It is easy to see that $|E(P,S)|\le k-2$ and thus $|P|\ge k+2$. If $|Q|\le k-1$, then $|E(Q,S)|\ge (k+1-|Q|)|Q|\ge 2k-2$, which is impossible. It implies $|Q|\ge k$. Set $|E(P,S)|=a\le k-2, |P|=p\ge k+2, |E(Q,S)|=b, |Q|=q\ge k, n-p-q=r\ge 2$. Partition V(G) into three parts $P,V(G)-P-Q,Q$ respectively. The corresponding quotient matrix B is

$$\begin{aligned} \left( \begin{array}{ccc} k-\frac{a}{p}&{}\quad \frac{a}{p}&{}\quad 0\\ \frac{a}{r}&{}\quad k-\frac{a+b}{r}&{}\quad \frac{b}{r}\\ 0&{}\quad \frac{b}{q}&{}\quad k-\frac{b}{q} \end{array}\right) . \end{aligned}$$

It is easy to check that the characteristic polynomial of B is $f_{\lambda }(B)=(\lambda -k)\left[ \lambda ^{2}-\left( 2k-\frac{a}{p} -\frac{b}{q}-\frac{a+b}{r}\right) \lambda +\left( k-\frac{a}{p}\right) \left( k-\frac{b}{q}\right) -\left( k-\frac{a}{p}\right) \frac{b}{r}-\left( k-\frac{b}{q}\right) \frac{a}{r}\right]$. By Theorem 2.2 and a routine computing, we have $\lambda _{2}(G)\ge k+$$\frac{\sqrt{\left( \frac{a}{p}-\frac{b}{q}\right) ^{2} +2\frac{a-b}{r}\left( \frac{a}{p}-\frac{b}{q}\right) +\left( \frac{a+b}{r}\right) ^{2}} -\left( \frac{a}{p}+\frac{b}{q}+\frac{a+b}{r}\right) }{2}$.

Now consider the function $g(x)=\sqrt{\left( \frac{a}{p}-\frac{b}{q}\right) ^{2}+2x(a-b)\left( \frac{a}{p} -\frac{b}{q}\right) +((a+b)x)^{2}}-(a+b)x$, where $x=\frac{1}{r}\le \frac{1}{2}$. It is easy to check that $g^{'}(x)=\frac{(a+b)^{2}x+(a-b)\left( \frac{a}{p}-\frac{b}{q}\right) }{\sqrt{\left( \frac{a}{p}-\frac{b}{q}\right) ^{2}+2x(a-b)\left( \frac{a}{p} -\frac{b}{q}\right) +((a+b)x)^{2}}}-(a+b)\le 0$ whenever $(a-b)^{2}\left( \frac{a}{p}-\frac{b}{q}\right) \le (a+b)^{2}\left( \frac{a}{p}-\frac{b}{q}\right)$. It is obviously satisfied and thus g(x) is decreasing for $x\ge 0$. Then $\lambda _{2}(G)\ge k+\frac{\sqrt{\left( \frac{a}{p}-\frac{b}{q}\right) ^{2}+(a-b)\left( \frac{a}{p} -\frac{b}{q}\right) +\left( \frac{a+b}{2}\right) ^{2}}-\left( \frac{a}{p}+\frac{b}{q}+\frac{a+b}{2}\right) }{2}$, since $r\ge 2$.

Now consider the function $h(x)=\sqrt{\left( ax-\frac{b}{q}\right) ^{2}+(a-b)\left( ax-\frac{b}{q}\right) +\left( \frac{a+b}{2}\right) ^{2}}-ax$, where $x=\frac{1}{p}$. It is easy to check that $h^{'}(x)=\frac{2a\left( ax-\frac{b}{q}\right) +a(a-b)}{2\sqrt{\left( ax-\frac{b}{q}\right) ^{2} +(a-b)\left( ax-\frac{b}{q}\right) +\left( \frac{a+b}{2}\right) ^{2}}}-a\le 0$ whenever $(a-b)^{2}\le (a+b)^{2}$. It is obviously satisfied, and thus we have that the expression $k+\frac{\sqrt{\left( \frac{a}{p}-\frac{b}{q}\right) ^{2}+(a-b)\left( \frac{a}{p} -\frac{b}{q}\right) +\left( \frac{a+b}{2}\right) ^{2}}-\left( \frac{a}{p}+\frac{b}{q}+\frac{a+b}{2}\right) }{2}$ is increasing with respect to p and also to q, since the two pairs (a, p) and (b, q) are symmetric in the expression. Therefore, we have $\lambda _{2}(G)\ge k+\frac{\sqrt{\left( \frac{a}{k+2}-\frac{b}{k}\right) ^{2}+(a-b)\left( \frac{a}{k+2} -\frac{b}{k}\right) +\left( \frac{a+b}{2}\right) ^{2}}-\left( \frac{a}{k+2}+\frac{b}{k}+\frac{a+b}{2}\right) }{2}$, since $p\ge k+2, q\ge k$. Since $(a-b)\left( \frac{a}{k+2}-\frac{b}{k}\right) \ge 0$ (Notice that $a\le b$), we have $\lambda _{2}(G)\ge k+\frac{\sqrt{\left( \frac{a+b}{2}\right) ^{2}}-\left( \frac{a}{k+2}+\frac{b}{k}+\frac{a+b}{2}\right) }{2}\ge k-\frac{a}{2(k+2)}-\frac{2k-2-a}{2k}$ (Notice that $a+b\le 2k-2$). Partition V(G) into two parts P and $V(G)-P$, respectively. By Theorem 2.2, we have $\lambda _{2}(G)\ge k-\frac{a}{p}-\frac{a}{n-p}$. Since $p\ge k+2,n-p\ge k+2$, thus we have $\lambda _{2}(G)\ge k-\frac{a}{k+2}-\frac{a}{k+2}$. Therefore, we have $\lambda _{2}(G)\ge max\left\{ k-\frac{a}{2(k+2)}-\frac{2k-2-a}{2k},k-\frac{2a}{k+2}\right\} \ge k-1+\frac{3}{2k+1}$ (when $a=\frac{(k-1)(k+2)}{2k+1}$). Since $\lambda _{2}(G)$ is an algebraic integer, thus $\lambda _{2}(G)> k-1+\frac{3}{2k+1}$, a contradiction.

Now we can suppose that there is precisely one non-singleton odd component, say P. By regularity, we have $o(G-S)=|S|\ge k$. Then $n\ge 3k+1$, since $|E(P,S)|<k$ and thus $|P|\ge k+2$. Set $|E(P,S)|=a\le k-2$ as a has the same parity with k, $|S|=s\ge k$ and $|P|=p\ge k+2$. Then $n=p+2s-1$. Partition V(G) into three parts $P,S,V(G)-P-S$, respectively. The corresponding quotient matrix C is

$$\begin{aligned} \left( \begin{array}{ccc} k-\frac{a}{p}&{}\quad \frac{a}{p}&{}\quad 0\\ \frac{a}{s}&{}\quad k-\frac{a}{s}-\frac{(s-1)k}{s}&{}\quad \frac{(s-1)k}{s}\\ 0&{}k&{}0 \end{array}\right) . \end{aligned}$$

It is easy to check that the characteristic polynomial of C is $f_{\lambda }(C)=(\lambda -k)\left[ \lambda ^{2}-\left( k-\frac{a}{p}-\frac{a}{s} -\frac{(s-1)k}{s}\right) \lambda -\left( k-\frac{a}{p}\right) \frac{(s-1)k}{s}\right]$. By Theorem 2.2 and a routine computing, we have $\lambda _{2}(G)\ge \frac{k-\frac{a}{p}-\frac{a}{s}-\frac{(s-1)k}{s} +\sqrt{\left( k-\frac{a}{p}+\frac{(s-1)k}{s}\right) ^{2}-\frac{2a}{s}\left( \frac{k}{s} -\frac{a}{p}-\frac{a}{2s}\right) }}{2}$.

Set $m=k-\frac{a}{p}+\frac{(s-1)k}{s}$. It is easy to see that $m\ge 2k-2$. Since $\frac{2a}{s}\left( \frac{k}{s}-\frac{a}{p}-\frac{a}{2s}\right) <\frac{2a}{s}\left( \frac{k}{s} -\frac{a}{2s}\right) \le \frac{k}{s}\le 1$, we have $\lambda _{2}(G)> \frac{k-\frac{a}{p}-\frac{a}{s}-\frac{(s-1)k}{s}+\sqrt{m^{2}-1}}{2}$. Since $\sqrt{m^{2}-1}\ge m-\frac{m}{2m^{2}-1}\ge m-\frac{2k-2}{2(2k-2)^{2}-1}$, we have $\lambda _{2}(G)> \frac{k-\frac{a}{p}-\frac{a}{s}-\frac{(s-1)k}{s}+ m-\frac{2k-2}{2(2k-2)^{2}-1}}{2}=k-\frac{a}{p}-\frac{a}{2s}-\frac{k-1}{2(2k-2)^{2}-1}$. Since $\frac{a}{p}+\frac{a}{2s}=\frac{a(2s+p)}{2sp}=\frac{a(n+1)}{p(n+1-p)}\le \frac{(k-2)(n+1)}{(k+2)(n-k-1)}$ (Notice that $a\le k-2$ and $k+2\le p=n+1-2s\le n+1-2k$), we have $\lambda _{2}(G)>k-\frac{(k-2)(n+1)}{(k+2)(n-k-1)} -\frac{k-1}{2(2k-2)^{2}-1}=k-1+\frac{4}{k+2}-\frac{k-1}{8(k-1)^{2}-1} -\frac{k-2}{n-k-1}$, a contradiction. (Notice that for $2k+4\le n\le 3k-1$ we must have $|S|=2$, which implies that we need only to consider the case in which $G-S$ has only two non-singleton components.) We now complete the proof of (i).

(ii) For even integer $k\ge 4$, the proof is very similar to case (i) and thus omitted, since we need only to change slightly when we consider the parity of the subsets of V(G) and k. We complete the proof. $\square$

Remark 2.2

When k is large, the bound in Theorem 2.4 is convenient to use. When $k\ge 3$ is small, the bound in Theorem 2.5 is good enough to use. Moreover, if n is not down close to 3k (or $3k+1$), the bound in Theorem 2.5 is obviously better than the bound in Theorem 2.4. (Checking the proofs of Theorems 2.4 and 2.5, we believe that Theorem 2.4 is also true for $4\le k\le 18$, of which the strict proof contains much more computing even by computer. For a cubic graph G, by Theorem 2.1 it is easy to see that G is 1-extendable if and only if G has no cut edges. Let H be the cubic graph obtained from two copies of $K_{4}$ by putting one new vertex in an edge of each copy of $K_{4}$ and then connecting the two new vertices. In [4], it showed that H has the smallest second largest eigenvalue among the cubic graphs with cut edges.)

3 Bi-critical Regular Graphs from Eigenvalues

Let $k\ge 3$ be an odd integer. Let $A=\overline{K_{k}}$, $B=\overline{K_{k-1}}$ and $C=K_{k}$, respectively. Define a graph $N_{k}$ with the three parts A, B and C by adding a perfect matching between A and C, and also adding an edge between each vertex in A and each vertex in B . Thus $N_{k}$ is a k-regular graph on $3k-1$ vertices.

Let $k\ge 4$ be an even integer. Let $A=\overline{K_{k}}$, $B=\overline{K_{k-1}}$ and $C=\overline{M_{k}}+K_{1}$, respectively. Define a graph $N_{k}$ with the three parts A, B and C by adding a perfect matching between A and the set of vertices of degree $k-1$ in C, and also adding an edge between each vertex in A and each vertex in B. Thus $N_{k}$ is a k-regular graph on 3k vertices. (Notice that the polynomial $f_{k}(\lambda )$ defined in the following is not the one defined in Sect. 2.)

Theorem 3.1

Let $N_{k}$ be the graph defined above for $k\ge 3$. Then $N_{k}$ is not bi-critical and we also have the followings.

• (i) If $k\ge 3$ is an odd integer, then we have $k-\frac{3}{2}+\frac{1}{8k}<\lambda _{2}(N_{k})=\frac{\sqrt{1+4(k-1)^{2}}-1}{2}<k-\frac{3}{2}+\frac{1}{8k}+\frac{1}{8k(k-1)}$.

• (ii) If $k\ge 4$ is an even integer, then $\lambda _{2}(N_{k})$ is the largest root of polynomial $f_{k}(\lambda )=\lambda ^{3}+2\lambda ^{2}-(k^{2}-2k+1)\lambda -k^{2}+k$. Moreover, we have $k-\frac{3}{2}+\frac{9}{8k}<\lambda _{2}(N_{k})<k-\frac{3}{2} +\frac{9}{8k}+\frac{3}{4k(2k-3)}$ for $k\ge 4$.

Proof

For any integer $k\ge 3$, since $o(N_{k}-A)=k=|A|$, thus for any two vertices u, v in A the graph $N_{k}-u-v$ has no perfect matching by Theorem 2.1. Therefore, $N_{k}$ is not bi-critical.

(i) Let $k\ge 3$ be an odd integer. Partition $H_{k}$ into three parts $V_{1}=A$, $V_{2}=B$ and $V_{3}=C$, respectively. It is easy to see that this partition is equitable. The quotient matrix is equal to

$$\begin{aligned} \left( \begin{array}{ccc} 0&{}\quad k-1&{}\quad 1\\ k&{}\quad 0&{}\quad 0\\ 1&{}\quad 0&{}\quad k-1 \end{array}\right) . \end{aligned}$$

Similar to the proof of Theorem 2.3, we have the conclusion.

(ii) Let $k\ge 4$ be an even integer. Partition $H_{k}$ into four parts $V_{1}=A,V_{2}=B,V_{3}=\overline{M_{k}}$ (Notice that $C=\overline{M_{k}}+K_{1}$) and $V_{4}=C-V_{3}$, respectively. It is easy to see that this partition is equitable. The quotient matrix is equal to

$$\begin{aligned} \left( \begin{array}{cccc} 0&{}\quad k-1&{}\quad 1&{}\quad 0\\ k&{}\quad 0&{}\quad 0&{}\quad 0\\ 1&{}\quad 0&{}\quad k-2&{}\quad 1\\ 0&{}\quad 0&{}\quad k&{}\quad 0 \end{array}\right) . \end{aligned}$$

The characteristic polynomial of this matrix is equal to $(\lambda -k)f_{k}(\lambda )$. Let $p_{k}$ be the largest root of $f_{k}(\lambda )$. Set $\lambda =k-\frac{3}{2}+\frac{y}{k}$, where $0\le y<\frac{3k}{2}$. Then we have $f_{k}(\lambda )=(2y-\frac{9}{4})k+\left( \frac{21}{8}-3y\right) +\frac{3y^{2}-\frac{1}{4}y}{k}-\frac{\frac{5}{2}y^{2}}{k^{2}}+\frac{y^{3}}{k^{3}}$$(***)$ by a routine computing. It is easy to check that the sum of first two terms of $(***)$ is nonnegative for $y\ge \frac{9}{8}+\frac{3}{4(2k-3)}$, and the sum of the following two terms of $(***)$ is positive for $y\ge 1$. Therefore, $f_{k}\left( k-\frac{3}{2}+\frac{y}{k}\right) >0$ for $y\ge \frac{9}{8}+\frac{3}{4(2k-3)}$, which implies $p_{k}<k-\frac{3}{2}+\frac{9}{8k}+\frac{3}{4k(2k-3)}$ for $k\ge 4$. It can be directly checked that $f_{k}\left( k-\frac{3}{2}+\frac{9}{8k}\right) <0$ for $k\ge 4$, which implies $p_{k}>k-\frac{3}{2}+\frac{9}{8k}$ for $k\ge 4$. Therefore, we have $k-\frac{3}{2}+\frac{9}{8k}<p_{k}<k-\frac{3}{2}+\frac{9}{8k}+\frac{3}{4k(2k-3)}$ for $k\ge 4$. Similar to the proof of Theorem 2.3, we can show that $\lambda _{2}(N_{k})=p_{k}$. We complete the proof. $\square$

For a bipartite regular graph G with two parts X and Y, it is easy to see that $|X|=|Y|$. Since for any two vertices u, v in X the graph $G-u-v$ has no perfect matching by Theorem 2.1, thus G is not bi-critical. Then we need only to consider non-bipartite regular graphs in the following discussion.

Theorem 3.2

Let G be a non-bipartite connected regular graph of degree $k\ge 3$ on even number n of vertices. If $\lambda _{2}(G)<\lambda _{2}(N_{k})$, then G is bi-critical.

Proof

We prove the conclusion by contradiction. Suppose that G is not bi-critical. Then there are two vertices x, y of G such that $G-x-y$ has no perfect matching. By Theorem 2.1, there is a subset $S_{0}$ of $V(G-x-y)$ such that $o(G-x-y-S_{0})>|S_{0}|$, and thus $o(G-x-y-S_{0})\ge |S_{0}|+2$ by parity. Let $S=S_{0}\bigcup \left\{ x,y\right\}$. Then $o(G-S)\ge |S|$. Choose the maximal S such that $o(G-S)\ge |S|$. By the choice of S, there is no even component in $G-S$. Similar to the proof of Theorem 2.4, we can show that $o(G-S)=|S|$.

(i) Suppose that $k\ge 3$ is an odd integer. If there are at least two odd components of $G-S$ which are not singleton components, then there exist two non-singleton components, say P and Q, such that $|E(P,S)|\le |E(Q,S)|$ and $|E(P,S)|+|E(Q,S)|\le 2k$ by regularity. Thus $|E(P,S)|\le k$ and $|P|\ge k$. If $|Q|<k$ and thus $|Q|\le k-2$, then $|E(Q,S)|\ge 3k-6$ as $|Q|\ge 3$. Since $|E(P,S)|+|E(Q,S)|\le 2k$, we have $k=5$, $|Q|=k-2=3$. It follows that $|E(P,S)|=1$ and thus $|P|\ge k+2$. Partition V(G) into two parts P and $\overline{P}$, respectively. By Theorem 2.2 we have $\lambda _{2}(G)>k-\frac{2}{k+2}>k-\frac{3}{2}+\frac{1}{8k} +\frac{1}{8k(k-1)}>\lambda _{2}(N_{k})$, a contradiction. Therefore, $|Q|\ge k$. Set $|E(P,S)|=a\le k$. By Theorem 2.2, we have $\lambda _{2}(G)\ge min\left\{ \lambda _{1}(P),\lambda _{1}(Q)\right\} \ge min\left\{ k-\frac{a}{k},k-\frac{2k-a}{k}\right\} = k-\frac{2k-a}{k}$. Partition V(G) into two parts P and $\overline{P}$, respectively. By Theorem 2.2 we have $\lambda _{2}(G)\ge k-\frac{a}{k}-\frac{a}{k+2}$. Therefore, we have $\lambda _{2}(G)\ge max\left\{ k-\frac{2k-a}{k}, k-\frac{a}{k}-\frac{a}{k+2}\right\} \ge k-\frac{4k+4}{3k+4}$ (when $a=\frac{2k^{2}+4k}{3k+4}$). By a routine computing, $k-\frac{4k+4}{3k+4}\ge k-\frac{3}{2}+\frac{1}{8k}+\frac{1}{8k(k-1)}$ for $k\ge 3$. Thus $\lambda _{2}(G)>\lambda _{2}(N_{k})$ for $k\ge 3$, a contradiction.

Now we can suppose that there is precisely one non-singleton odd component, say P, since G is not a bipartite graph. It follows that $o(G-S)=|S|\ge k$ and $n\ge 3k-1$, since $|E(P,S)|\le k$ and thus $|P|\ge k$. Set $|E(P,S)|=a$. If $a<k$ and thus $a\le k-2$ by parity, partition V(G) into two parts P and $\overline{P}$, respectively. By Theorem 2.2 we have $\lambda _{2}(G)\ge k-\frac{a}{|P|}-\frac{a}{n-|P|}\ge k-\frac{k-2}{k}-\frac{k-2}{2k-1}$ as $|P|\ge k, n-|P|\ge k$ and $n\ge 3k-1$. By a routine computing, $k-\frac{k-2}{k}-\frac{k-2}{2k-1}\ge k-\frac{3}{2}+\frac{1}{8k}+\frac{1}{8k(k-1)}$ if and only if $42k^{2}-59k+16\ge 0$. It is satisfied for $k\ge 3$, and thus $\lambda _{2}(G)>\lambda _{2}(N_{k})$ for $k\ge 3$, a contradiction. Now suppose $|E(P,S)|=a=k$.

If $n=3k-1$, then $|P|=k$ and $|S|=k$. Consequently, the graph G is isomorphic to $N_{k}$, which is contradictive to the fact that $\lambda _{2}(G)<\lambda _{2}(N_{k})$.

Suppose $n\ge 3k+1$. Partition V(G) into two parts P and $\overline{P}$, respectively. By Theorem 2.2 we have $\lambda _{2}(G)\ge k-\frac{k}{|P|}-\frac{k}{n-|P|}\ge k-\frac{k}{k}-\frac{k}{2k+1}$ as $|P|\ge k, n-|P|\ge k$ and $n\ge 3k+1$. It is easy to see that $k-\frac{k}{k}-\frac{k}{2k+1}\ge k-\frac{3}{2}+\frac{1}{8k}+\frac{1}{8k(k-1)}$ for $k\ge 3$, and thus $\lambda _{2}(G)>\lambda _{2}(N_{k})$ for $k\ge 3$, a contradiction.

(ii) Let $k\ge 4$ be an even integer. If there are at least two odd components of $G-S$ which are not singleton components, then there exist two non-singleton components, say P and Q, such that $|E(P,S)|\le |E(Q,S)|$ and $|E(P,S)|+|E(Q,S)|\le 2k$ by regularity. Thus $|E(P,S)|\le k$ and $|P|\ge k+1$. If $|Q|< k+1$ and thus $|Q|\le k-1$, then $|E(Q,S)|\ge 2k-2$ as $|Q|\ge 3$. Since $|E(P,S)|+|E(Q,S)|\le 2k$, we have $|Q|=k-1$ and $|E(P,S)|=2$. Partition V(G) into two parts P and $\overline{P}$, respectively. By Theorem 2.2 we have $\lambda _{2}(G)>k-\frac{4}{k+1}$. By a routine computing, $k-\frac{4}{k+1}>k-\frac{3}{2}+\frac{9}{8k}+\frac{3}{4k(2k-3)}(>\lambda _{2}(N_{k}))$ if and only if $24k^{3}-94k^{2}+63k+21>0$. It is satisfied for $k\ge 4$, a contradiction. Therefore, $|Q|\ge k+1$. Set $|E(P,S)|=a\le k$. By Theorem 2.2 we have $\lambda _{2}(G)\ge min\left\{ \lambda _{1}(P),\lambda _{1}(Q)\right\} \ge min\left\{ k-\frac{a}{k+1},k-\frac{2k-a}{k+1}\right\} = k-\frac{2k-a}{k+1}$. Partition V(G) into two parts P and $\overline{P}$, respectively. By Theorem 2.2 we have $\lambda _{2}(G)\ge k-\frac{a}{k+1}-\frac{a}{k+3}$ as $|P|\ge k+1$ and $|\overline{P}|\ge k+3$. Therefore, we have $\lambda _{2}(G)\ge max\left\{ k-\frac{2k-a}{k+1},k-\frac{a}{k+1}-\frac{a}{k+3}\right\} \ge k-\frac{4k^{2}+4k}{3k^{2}+10k+7}$ (when $a=\frac{2k^{2}+6k}{3k+7}$). By a routine computing, $k-\frac{4k^{2}+4k}{3k^{2}+10k+7}\ge k-\frac{3}{2}+\frac{9}{8k}+\frac{3}{4k(2k-3)}$ if and only if $8k^{4}+110k^{3}-213k^{2}-168k+147\ge 0$. It is satisfied for $k\ge 4$, and thus $\lambda _{2}(G)>\lambda _{2}(N_{k})$ for $k\ge 4$, a contradiction.

Now we can suppose that there is precisely one non-singleton odd component, say P, since G is not a bipartite graph. It follows that $o(G-S)=|S|\ge k$ and $n\ge 3k$, since $|E(P,S)|\le k$ and thus $|P|\ge k+1$. Set $|E(P,S)|=a$. If $a<k$ and thus $a\le k-2$ by parity, partition V(G) into two parts P and $\overline{P}$, respectively. By Theorem 2.2 we have $\lambda _{2}(G)\ge k-\frac{a}{|P|}-\frac{a}{n-|P|}\ge k-\frac{k-2}{k+1}-\frac{k-2}{2k-1}$ as $|P|\ge k+1, n-|P|\ge k+1$ and $n\ge 3k$. By a routine computing, $k-\frac{k-2}{k+1}-\frac{k-2}{2k-1}\ge k-\frac{3}{2}+\frac{9}{8k}+\frac{3}{4k(2k-3)}$ if and only if $28k^{3}-60k^{2}+25k-7\ge 0$. It is satisfied for $k\ge 4$, and thus $\lambda _{2}(G)>\lambda _{2}(N_{k})$ for $k\ge 4$, a contradiction. Now suppose $|E(P,S)|=a=k$.

If $n=3k$, then $|P|=k+1$ and $|S|=k$. Let $V_{4}^{'}$ be a vertex of degree k in G[P] (compared with the set $V_{4}=K_{1}$ in the partition of $N_{k}$). Similarly, G has a partition which contains four parts (compared with $N_{k}$) such that the quotient matrices of G and $N_{k}$ are the same. By Theorem 2.2, we have $\lambda _{2}(G)\ge \lambda _{2}(N_{k})$, a contradiction.

Suppose $n=3k+2$. If $|S|=k$, then $|P|=k+3$. Partition the graph G into two parts P and $\overline{P}$, respectively. By Theorem 2.2 we have $\lambda _{2}(G)\ge k-\frac{k}{|P|}-\frac{k}{n-|P|}\ge k-\frac{k}{k+3}-\frac{k}{2k-1}$ as $|P|\ge k+3, n-|P|\ge k+3$ and $n=3k+2$. By a routine computing, $k-\frac{k}{k+3}-\frac{k}{2k-1}\ge k-\frac{3}{2}+\frac{9}{8k}+\frac{3}{4k(2k-3)}$ if and only if $52k^{3}-252k^{2}+267k-63\ge 0$. It is satisfied for $k\ge 4$, and thus $\lambda _{2}(G)>\lambda _{2}(N_{k})$ for $k\ge 4$, a contradiction. If $|S|=k+1$, then $|P|=k+1$. Partition the graph G into three parts $S, V(G)-S-P$ and P, respectively. The quotient matrix is equal to

$$\begin{aligned} \left( \begin{array}{ccc} 0&{}\quad \frac{k^{2}}{k+1}&{}\quad \frac{k}{k+1}\\ k&{}\quad 0&{}\quad 0\\ \frac{k}{k+1}&{}0&{}k-\frac{k}{k+1} \end{array}\right) . \end{aligned}$$

Its characteristic polynomial is equal to $(\lambda -k)g(\lambda )$, where $g(\lambda )=\lambda ^{2}+\frac{k}{k+1}\lambda +\frac{k^{4}}{(k+1)^{2}}$. By a routine computing, we have $(k+1)^{3}f_{k}(\lambda )-[(k+1)^{3}\lambda +(k+2)(k+1)^{2}] g(\lambda )=(k^{3}-k^{2}-3k-1)\lambda +2k^{2}+k>0$ for $k\ge 4$ and $\lambda \ge 0$. It implies $g(\lambda _{2}(N_{k}))<0$ and thus $\lambda _{2}(N_{k})$ is less than the largest root of $g(\lambda )$. By Theorem 2.2 we have $\lambda _{2}(G)>\lambda _{2}(N_{k})$, a contradiction.

Suppose $n\ge 3k+4$. Partition V(G) into two parts P and $\overline{P}$, respectively. By Theorem 2.2 we have $\lambda _{2}(G)\ge k-\frac{k}{|P|}-\frac{k}{n-|P|}\ge k-\frac{k}{k+1}-\frac{k}{2k+3}$ as $|P|\ge k+1, n-|P|\ge k+1$ and $n\ge 3k+4$. By a routine computing, $k-\frac{k}{k+1}-\frac{k}{2k+3}\ge k-\frac{3}{2}+\frac{9}{8k}+\frac{3}{4k(2k-3)}$ if and only if $20k^{3}-60k^{2}-57k+63\ge 0$. It is satisfied for $k\ge 4$, and thus $\lambda _{2}(G)>\lambda _{2}(N_{k})$ for $k\ge 4$, a contradiction. We complete the proof. $\square$

4 The Connectivity of Regular Graphs from Eigenvalues

It showed that the connectivity of a graph (which is not a complete graph) is not less than its algebraic connectivity in [9]. Here, the algebraic connectivity of a k-regular graph G is equal to $k-\lambda _{2}(G)$. This result usually can not be improved. In fact, if $2\ell -2\ge k$ and $k\ell$ is even, then there exists a k-regular graph G such that both the connectivity and the algebraic connectivity of G are equal to $\ell$ (referring to [4]). For the case $1\le \ell <\frac{k+2}{2}$, we give the following result which is obviously an improvement of the result in [9].

Theorem 4.1

Let G be a connected regular graph of degree $k\ge 3$. For any integer $1\le \ell <\frac{k+2}{2}$, if $\lambda _{2}(G)\le k-\frac{\ell }{2}\frac{k}{k-\ell +1}$, then G is $(\ell +1)$-connected.

Proof

Suppose that G is not $(\ell +1)$-connected. Then there exists a subset $A\subseteq V(G)$ of size $\ell$ such that $G-A$ is not connected. Let m be the number of edges in G[A]. Suppose that the components of $G-A$ are $P_{1},P_{2},\ldots ,P_{s}$, respectively, where $s\ge 2$. By regularity, $|P_{i}|\ge k-\ell +1$ for each $1\le i\le s$.

Let $P=P_{1}$ and $Q=P_{2}\bigcup P_{3}\bigcup \cdots \bigcup P_{s}$. Therefore, $|P|,|Q|\ge k-\ell +1$. Partition V(G) into three parts A, P, Q, respectively. The quotient matrix is

$$\begin{aligned} \left( \begin{array}{ccc} \frac{2m}{\ell }&{}\quad \frac{a}{\ell }&{}\quad \frac{b}{\ell }\\ \frac{a}{p}&{}\quad k-\frac{a}{p}&{}\quad 0\\ \frac{b}{q}&{}\quad 0&{}\quad k-\frac{b}{q} \end{array}\right) , \end{aligned}$$

where $p=|P|,q=|Q|$, $a=|E(P,A)|$ and $b=|E(Q,A)|$. The characteristic polynomial of this quotient matrix is $(\lambda -k)(\lambda ^{2}+\left( \frac{a}{p}+\frac{b}{q}-k-\frac{2m}{\ell }\right) \lambda +\frac{2mk}{\ell }+\frac{ab}{pq}-\frac{a^{2}+2ma}{p\ell } -\frac{b^{2}+2mb}{q\ell })$. By Theorem 2.2 and a routine computing, we have $\lambda _{2}(G)\ge \frac{k+\frac{2m}{\ell }-\frac{a}{p}-\frac{b}{q} +\sqrt{\left( k-\frac{2m}{\ell }\right) ^{2}+\frac{2}{\ell }(b-a)\left( \frac{b}{q} -\frac{a}{p}\right) +\left( \frac{b}{q}-\frac{a}{p}\right) ^{2}}}{2}$ as $a+b=k\ell -2m$.

Let $g(x)=-bx+\sqrt{\left( k-\frac{2m}{\ell }\right) ^{2}+\frac{2}{\ell }(b-a)(bx-\frac{a}{p}) +(bx-\frac{a}{p})^{2}}$. By a routine computing we have $g^{'}(x)=-b+\frac{\frac{2}{\ell }b(b-a)+2b(bx-\frac{a}{p})}{2\sqrt{\left( k-\frac{2m}{\ell }\right) ^{2}+\frac{2}{\ell }(b-a)(bx-\frac{a}{p}) +(bx-\frac{a}{p})^{2}}}<0$ whenever $\left( \frac{b-a}{\ell }\right) ^{2}<\left( k-\frac{2m}{\ell }\right) ^{2}$. It is obviously satisfied as $a+b=k\ell -2m$.

It follows that the expression $\frac{k+\frac{2m}{\ell }-\frac{a}{p}-\frac{b}{q} +\sqrt{\left( k-\frac{2m}{\ell }\right) ^{2}+\frac{2}{\ell }(b-a)\left( \frac{b}{q} -\frac{a}{p}\right) +\left( \frac{b}{q}-\frac{a}{p}\right) ^{2}}}{2}$ is strictly increasing with respect to q and also to p, since the two pairs (a, p) and (b, q) are symmetric in the expression. Since $p=|P|\ge k-\ell +1$ and $q=|Q|\ge k-\ell +1$, thus $\lambda _{2}(G)\ge \frac{k+\frac{2m}{\ell }-\frac{a}{k-\ell +1}-\frac{b}{k-\ell +1} +\sqrt{\left( k-\frac{2m}{\ell }\right) ^{2}+\frac{2}{\ell }\frac{(b-a)^{2}}{k-\ell +1} +\left( \frac{b-a}{k-\ell +1}\right) ^{2}}}{2}$$\ge k-\frac{k\ell -2m}{2(k-\ell +1)}\ge k-\frac{\ell }{2}\frac{k}{k-\ell +1}$. Moreover, if the equality is satisfied, then $|P|=|Q|=k-\ell +1$, $m=0$ and $a=b=\frac{k\ell }{2}$. By regularity we have $k=2(k-\ell +1)$ or $\ell =\frac{k+2}{2}$, a contradiction. It follows that $\lambda _{2}(G)>k-\frac{\ell }{2}\frac{k}{k-\ell +1}$, a contradiction. We complete the proof. $\square$

Remark 4.1

Let G be a regular graph of degree $k\ge 3$. At the end of reference [4], there is a remark about $\lambda _{2}(G)\le k-\frac{1}{2}$ implying that G is 2-connected. It is obviously true by letting $\ell =1$ in Theorem 4.1. Moreover, this bound is always tight. For example, if $k=4m$ for some positive integer m, let $B=C=K_{k+1-\frac{k}{2}}+\overline{M_{\frac{k}{2}}}$ and $A=u$ (an isolated vertex). Define a new graph $G_{k}$ formed by joining the vertex u to each vertex of degree $k-1$ in B and in C respectively. Thus $G_{k}$ is a k-regular graph with a cut vertex u. Obviously, $G_{k}$ has an equitable partition which contains five parts. By Theorem 2.2, it is not difficult to show that $\lambda _{2}(G_{k})<k-\frac{1}{2}+\frac{3}{4k}$, as required.