\documentclass[12pt]{article} \usepackage{e-jc} \specs{}{}{} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf The extendability of matchings\\ in strongly regular graphs} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Sebastian M. Cioab\u{a}\thanks{Research supported in part by National Security Agency grant H98230-13-1-0267.}\\ \small Department of Mathematical Sciences\\[-0.8ex] \small University of Delaware\\[-0.8ex] \small Newark, DE 19707-2553, U.S.A.\\ \small\tt cioaba@math.udel.edu\\ \and \qquad Weiqiang Li\\ \small Department of Mathematical Sciences\\[-0.8ex] \small University of Delaware\\[-0.8ex] \small Newark, DE 19707-2553, U.S.A.\\ \small\tt weiqiang@udel.edu } \date{\dateline{Feb 25, 2014}{Apr 28, 2014}{}\\ \small Mathematics Subject Classifications: 05E30, 05C50, 05C70} \begin{document} \maketitle \begin{abstract} A graph $G$ of even order $v$ is called $t$-extendable if it contains a perfect matching, $tk/2$), where $\lambda$ is the number of common neighbors of any two adjacent vertices and $\mu$ is the number of common neighbors of any two non-adjacent vertices. Our results are close to being best possible as there are strongly regular graphs of valency $k$ that are not $\lceil k/2\rceil $-extendable. We show that the extendability of many strongly regular graphs of valency $k$ is at least $\lceil k/2 \rceil -1$ and we conjecture that this is true for all primitive strongly regular graphs. We obtain similar results for strongly regular graphs of odd order. % keywords are optional \bigskip\noindent \textbf{Keywords:} strongly regular graphs; matchings; extendability; Triangular graphs; Latin square graphs; Block graphs of Steiner systems \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} A set of edges $M$ of a graph $G$ is a matching if no two edges of $M$ share a vertex. A matching $M$ is perfect if every vertex is incident with exactly one edge of $M$. A matching is near perfect if all but one of the vertices of $G$ are incident with edges of the matching. A graph $G$ of even order $v$ is called $t$-extendable if it contains at least one perfect matching, $tk/2$. This result is close to being best possible as we will prove that many connected strongly regular graphs with valency $k, \lambda\geq 1$ are not $\lceil k/2\rceil$-extendable. On the other hand, we also determine the extendability of many families of strongly regular graphs including Latin square graphs, block graphs of Steiner systems, triangular graphs, lattice graphs and all known triangle-free strongly regular graphs. For each graph of valency $k$ that we considered, the extendability is at least $\lceil k/2\rceil -1$. We conjecture that this is true for all primitive strongly regular graphs. We also obtain similar results for strongly regular graphs of odd order. \section{Main tools} In this section, we introduce the notation used in our paper and describe the main tools used in our proofs. For undefined terms, see Brouwer and Haemers \cite{BH2}. Let $o(G)$ denote the number of components of odd order of a graph $G$. If $S$ is a subset of vertices of $G$, then $G-S$ denotes the subgraph of $G$ obtained by deleting the vertices in $S$. The independence number of $G$ will be denoted by $\alpha(G)$. If $S$ and $T$ are vertex disjoint subsets of a graph, let $e(S,T)$ denote the number of edges with one endpoint in $S$ and the other in $T$. Let $N(T)$ denote the set of vertices outside $T$ that are adjacent to at least one vertex of $T$. When $T=\{x\}$, let $N(x)=N(\{x\})$. If $x$ is a vertex of a strongly regular graph $G$, let $N_2(x)=V(G)\setminus (\{x\}\cup N(x))$; the first subconstituent $\Gamma_1(x)$ of $x$ is the subgraph of $G$ induced by $N(x)$ and the second subconstituent $\Gamma_2(x)$ of $x$ is the subgraph of $G$ induced by $N_2(x)$. For a $(v,k,\lambda,\mu)$-srg $G$, let $k=\theta_1\geq \theta_2\geq \dots \geq \theta_v$ denote the eigenvalues of its adjacency matrix. It is known that $G$ has exactly three distinct eigenvalues $k,\theta_2$ and $\theta_v$ with $\theta_2+\theta_v=\lambda-\mu$ and $\theta_2\theta_v=\mu-k$ (see \cite{BH2,GR} for example). The complete multipartite graph which is the complement of $m$ disjoint copies of $K_a$ will be denoted by $K_{a\times m}$. \begin{theorem}[Tutte \cite{T}] A graph $G$ has a perfect matching if and only if $o(G-S)\leq |S|$ for every $S\subset V(G)$. \end{theorem} \begin{theorem}[Gallai \cite{Gallai}] A graph $G$ is factor-critical (or $0$-semi-extendable) if and only if $G$ has an odd number of vertices and $o(G-S)\leq |S|$ for all $\emptyset \not = S \subset V(G)$. \end{theorem} Using the above theorems, Yu \cite{Yu} obtained the following characterizations of graphs that are not $t$-extendable (resp. not $t$-semi-extendable). \begin{lemma}[Yu \cite{Yu}]\label{notn} Let $t\geq 1$ be an integer and $G$ be a graph containing a perfect matching. The graph $G$ is not $t$-extendable if and only if it contains a subset of vertices $S$ such that $S$ contains $t$ independent edges and $o(G-S)\geq |S|-2t+2$. \end{lemma} \begin{lemma}[Yu \cite{Yu}]\label{notn1/2} Let $t\geq 1$ be an integer and $G$ be a factor-critical graph. The graph $G$ is not $t$-semi-extendable if and only if it contains a subset of vertices $S$ such that $S$ contains $t$ independent edges, $|S|\geq 2t+1$, and $o(G-S)\geq |S|-2t+1$. \end{lemma} \begin{theorem}[Brouwer and Mesner \cite{BM}] \label{kconnected} If $G$ is a primitive strongly regular graph of valency $k$, then $G$ is $k$-connected. Any disconnecting set of size $k$ must be the neighborhood of some vertex. \end{theorem} \begin{lemma}\label{1connected} If $G$ is a distance-regular graph of degree $k\geq 2$ and diameter $D\geq 3$, then for any $x\in V(G)$, the subgraph induced by the vertices at distance $2$ or more from $x$, is connected. \end{lemma} \begin{proof} As $D\geq 3$, $G$ contains an induced path $P_4$ with $4$ vertices. By eigenvalue interlacing, the second largest eigenvalue $\theta_2(G)$ of $G$, is at least $\theta_2(P_4)=\frac{-1+\sqrt{5}}{2}>0$. Cioab\u{a} and Koolen \cite{CK} proved that if the $i$-th entry of the standard sequence corresponding to the second largest eigenvalue of a distance-regular graph $G$ is positive, then for any vertex $x$, the subgraph of $G$ induced by the vertices at distance at least $i$ from $x$ is connected. The second entry of the standard sequence corresponding to $\theta_2(G)$ is $\theta_2(G)/k>0$ and this finishes our proof. \end{proof} \begin{lemma}\label{Independentset} Let $G$ be a $(v,k,\lambda,\mu)$-srg with $\lambda \geq 1$. If $T$ is an independent set, then $|N(T)|\geq 2|T|$. \end{lemma} \begin{proof} For any $x\in N(T)$, $N(x)\cap T$ is an independent set in the subgraph $\Gamma_1(x)$ which is induced by $N(x)$. $\Gamma_1(x)$ is $\lambda$-regular. Consider the edges in $\Gamma_1(x)$. By counting the edges coming out of $N(x)\cap T$, we get that $|N(x)\cap T|\lambda\leq k\lambda/2$ and thus, $|N(x)\cap T|\leq k/2$. Therefore, $|T|k=e(T,N(T))=\sum_{x\in N(T)}|N(x)\cap T|\leq |N(T)|k/2$ implying $|N(T)|\geq 2|T|$. \end{proof} \begin{lemma}\label{Independentset2} Let $G$ be a $(v,k,\lambda,\mu)$-srg. If $T$ is an independent set, then \begin{equation} |N(T)|\geq \frac{k^2|T|}{k+|T|\mu-\mu}. \end{equation} \end{lemma} \begin{proof} For $x\in N(T)$, let $d_x=|T\cap N(x)|$ and $\bar{d}=\frac{\sum_{x\in N(T)} d_x}{|N(T)|}$. Counting the edges between $T$ and $N(T)$, we have $|T|k=|N(T)|\bar{d}$. Counting the $3$-subsets of the form $\{x,y,z\}$ such that $x, y \in T, z\in N(T), x\sim z, y \sim z$, we get that \begin{equation} {|T|\choose 2}\mu=\sum_{x\in N(T)} {d_x \choose 2}\geq |N(T)|{\bar{d} \choose 2} \end{equation} Combining these equations, we obtain that $(|T|-1)\mu\geq k\left(\frac{k|T|}{|N(T)|}-1\right)$ which implies the desired inequality $|N(T)|\geq \frac{k^2|T|}{k+|T|\mu-\mu}$. \end{proof} Note that the result of Lemma \ref{Independentset2} is better than the one obtained by applying Bonferroni's inequality $|N(T)|=|\cup_{x\in T}N(x)|\geq \sum_{x\in T}|N(x)|-\sum_{x\neq y\in T}|N(x)\cap N(y)|=kt-\mu{t\choose 2}$ when $t\geq 1+k/\mu$. \begin{lemma}\label{Independentset3} Let $G$ be a primitive $(v,k,\lambda,\mu)$-srg with $\lambda\geq 1$. If $T$ is an independent set, then \begin{equation} |N(T)|-|T|\geq \begin{cases} k-1 & \text{ if } 1\leq |T|\leq \frac{(k-\mu)(k-1)}{\mu} \text{ or if } |T|\geq k-1.\\ \frac{(k-2)[k(k-1)-(k-3)\mu]}{(k-3)\mu+k} & \text{ otherwise}. \end{cases} \end{equation} \end{lemma} \begin{proof} Define $f(x)=\frac{k^2x}{\mu x+k-\mu}-x$ for $x\geq 1$. Note that $f(1)=f\left(\frac{(k-\mu)(k-1)}{\mu}\right)=k-1$ and that $f'(x)=\frac{k^2(k-\mu)}{(\mu x+k-\mu)^2}-1$. Hence, $x_0=\frac{k\sqrt{k-\mu}-(k-\mu)}{\mu}$ is the only critical point of $f(x)$. Since $k-\mu>1$, we deduce that $10$ for $x\in [1,x_0)$ and $f'(x)<0$ for $x>x_0$. This implies that $|N(T)|-|T|\geq f(|T|)\geq f(1)=f\left(\frac{(k-\mu)(k-1)}{\mu}\right)=k-1$ whenever $1\leq |T|\leq \frac{(k-\mu)(k-1)}{\mu}$. If $|T|\geq k-1$, Lemma \ref{Independentset} implies that $|N(T)|-|T|\geq |T|\geq k-1$. If $\frac{(k-\mu)(k-1)}{\mu}<|T|\leq k-2$, then the previous arguments and Lemma \ref{Independentset2} imply that $|N(T)|-|T|\geq f(|T|)\geq f(k-2)=\frac{(k-2)[k(k-1)-(k-3)\mu]}{(k-3)\mu+k}$. \end{proof} Note that if $\lambda\geq 1$ and $\mu\leq k/2$, then Lemma \ref{Independentset3} implies that \begin{equation}\label{muk2} |N(T)|-|T|\geq k-1 \end{equation} for any independent set of vertices $T$. \begin{lemma}[Lemma 2.3 \cite{CKK}]\label{Haemers} Let $G$ be a connected $(v,k,\lambda,\mu)$-srg. Let $S$ be a disconnecting set of vertices of $G$ and denote by $A$ a subset of vertices of $G$ that induces a connected subgraph of $G - S$ and $B:=V(G) \setminus (A\cup S)$. If $|A|=a$ and $|B|=b$, then \begin{equation}\label{Eq1} |S|\geq \frac{4ab\mu}{(\lambda-\mu)^2+4(k-\mu)}. \end{equation} \end{lemma} The following lemma extends Theorem 5.1 of \cite{CKL}. \begin{lemma}\label{srgoutedge} Let $G$ be a primitive $(v,k,\lambda,\mu)$-srg. If $A$ is a subset of vertices with $3\leq |A| \leq v/2$ and $A^c$ denotes its complement, then \begin{equation} e(A, A^c) \geq 3k-6. \end{equation} \end{lemma} \begin{proof} If $k=3$, then $G$ is $K_{3,3}$ or the Petersen graph. If $G$ is $K_{3,3}$, the proof is immediate. If $G$ is the Petersen graph, and $A$ is a subset of vertices with $3\leq |A|\leq 4$, then the number of edges contained in $A$ is at most $|A|-1$ and therefore $e(A,A^c)\geq 3|A|-2(|A|-1)=|A|+2\geq 5$. If $|A|=5$, then the number of edges inside $A$ is at most $|A|=5$ and therefore $e(A,A^c)\geq 3|A|-2|A|=|A|=5$. If $k=4$, then $G$ is $K_{4,4}, K_{2,2,2}$ or the Lattice graph $L_2(3)$ which is the unique $(9,4,1,2)$-SRG. If $G$ is $K_{4,4}$ or $K_{2,2,2}$, the proof is immediate. If $G$ is the Lattice graph $L_2(3)$, and $A$ is a subset of vertices with $|A|=3$, then $e(A,A^c)\geq 6$ with equality if and only if $A$ induces a clique of order $3$. If $|A|=4$, then the number of edges contained in $A$ is at most $4$ and therefore, $e(A,A^c)\geq 4|A|-8=8$. Assume $k\geq 5$. If $|A|\leq k-2$, then $e(A,A^c)\geq |A|(k-|A|+1)\geq 3(k-2)$. Assume $|A|=k-1$. If every vertex of $A$ has at least $3$ neighbors outside $A$, then $e(A,A^c)\geq 3(k-1)$. Otherwise, there exists a vertex $x\in A$ that has exactly $2$ neighbors outside $A$. Therefore, $e(N(x)\cap A^c,A) \geq 2+2(\lambda-1)=2\lambda$. Each vertex in $N(x)$ has $k-\lambda-1$ neighbors outside $\{x\}\cup N(x)$. Thus, $e(N(x)\cap A, V(G)\setminus (N(x)\cup \{x\}))\geq (k-2)(k-\lambda -1)$. Hence, $e(A,A^c)\geq (k-2)(k-\lambda-1)+2\lambda\geq 3(k-2)$ since $\lambda\leq k-2$. If $k\leq |A|\leq v/2$, then $e(A,A^c)\geq \frac{(k-\theta_2)|A|(v-|A|)}{v}\geq \frac{(k-\theta_2)k}{2}$ (see \cite[Corollary 4.8.4]{BH2} or \cite{Mohar}). If $G$ is a conference graph of parameters $(4t+1,2t,t-1,t)$, then $k-\theta_2=\frac{4t+1-\sqrt{4t+1}}{2}>6$ for $t\geq 4$ and consequently, $e(A,A^c)>3k$. If $t=3$, $G$ has parameters $(13, 6, 2, 3)$ and therefore, $e(A, A^c)\geq \frac{(k-\theta_2)|A|(v-|A|)}{v}>\frac{(13-\sqrt{13})|A|(13-|A|)}{2\cdot 13}>12$. If $G$ is not a conference graph and $k-\theta_2\geq 6$, then $e(A,A^c)\geq 3k$ and we are done again. The only case left is when $G$ is not a conference graph and $k-\theta_2\leq 5$. In this case, the eigenvalues of $G$ are integers, $\theta_2\geq k-5$ and $\theta_v\leq -2$ as $G$ is not a complete graph. Since $k-1\geq k-\mu=\theta_2(-\theta_v)\geq 2k-10$, we get $5\leq k\leq 9$. If $\theta_v=-2$, then by Seidel's characterization of strongly regular graphs with minimum eigenvalue $-2$ (see \cite[Section 9.2]{BH2} or \cite{Seidel}), there are three cases to consider. If $G$ is a $(16,6,2,2)$-srg, then its second largest eigenvalue is $2$ and $e(A,A^c)\geq \frac{(k-\theta_2)|A|(v-|A|)}{v}=\frac{|A|(16-|A|)}{4}\geq 15$ for $k=6\leq |A|\leq 8=v/2$. If $G$ is a $(15,8,4,4)$-srg, then since $k>v/2$, $|A|\leq k-1$ and $e(A, A^c) \geq 3k-6$ by a previous case. If $G$ is a $(25,8,3,2)$-srg, then its second largest eigenvalue is $3$ and $e(A, A^c)\geq \frac{(k-\theta_2)|A|(v-|A|)}{v}=\frac{|A|(25-|A|)}{5}\geq 24$ for $k=8 \leq |A| \leq 12=\lfloor v/2\rfloor$. If $\theta_v\leq -3$, then we obtain $k-1\geq k-\mu=\theta_2(-\theta_v)\geq 3k-15$ which implies $5\leq k \leq 7$. If $k=5$, then $G$ is a $(16,5,0,2)$-srg whose second largest eigenvalue is $1$. Thus, $e(A,A^c)\geq \frac{(k-\theta_2)|A|(v-|A|)}{v}=\frac{|A|(16-|A|)}{4}\geq 13$ for $k=5\leq |A|\leq 8= \lfloor v/2\rfloor$. If $k=6$, then $G$ is a $(15,6,1,3)$-srg whose second largest eigenvalue is $1$. Thus, $e(A,A^c)\geq \frac{(k-\theta_2)|A|(v-|A|)}{v}=\frac{|A|(15-|A|)}{3} \geq 18$ for $k=6 \leq |A| \leq 7=\lfloor v/2\rfloor$. If $k=7$, then $G$ is a $(50,7,0,1)$-srg whose second largest eigenvalue is $2$. Therefore, $e(A,A^c)\geq \frac{(k-\theta_2)|A|(v-|A|)}{v}=\frac{|A|(50-|A|)}{10}\geq 28$ for $k=7 \leq |A| \leq 25=v/2$. This finishes our proof. \end{proof} \begin{lemma} If $G$ is a $(v,k,\lambda,\mu)$-srg of even order with independence number $2$, then the extendability of $G$ is $\lceil \frac{k}{2} \rceil -1$. \end{lemma} \begin{proof} The fact that the extendability is at least $\lceil \frac{k}{2} \rceil -1$ follows from Lemma \ref{notn}. If $G$ is imprimitive, then $G$ must be $K_{2\times m}$ for some $m$ and the conclusion will follow from Section 3.1. Assume that $G$ is primitive and $\alpha(G)=2$. For any vertex $x\in V$, let $N_2(x)=V(G)\setminus (\{x\}\cup N(x))$. The second subconstituent $\Gamma_2(x)$ must be a complete graph with $k-\mu+1$ vertices. As the clique number is at most $\lambda+2$, we have $\theta_2(-\theta_v)=k-\mu \leq \lambda+1$. Since $\theta_v \leq -2$, we obtain that $\theta_2 \leq \frac{\lambda+1}{2}\leq \lambda-1$ (when $\lambda \geq 3$). The first subconstituent $\Gamma_1(x)$ is $\lambda$-regular with second largest eigenvalue at most $\theta_2$. By \cite{CGH}, $\Gamma_1(x)$ contains a matching of size $\lfloor k/2\rfloor$. If $k$ is even, then this matching cannot be extended to a maximum matching of $G$. If $k$ is odd, one can add one disjoint edge to this matching such that the result matching of size $\lceil \frac{k}{2}\rceil$ cannot be extended to a maximum matching of $G$. It is easy to see that when $\lambda$ is $1$ or $2$, $\Gamma_1(x)$ contains a perfect matching or an almost perfect matching. \end{proof} \begin{lemma}\label{esrgindependence} If $G$ is a primitive $(v,k,\lambda,\mu)$-srg of even order with independence number $\alpha(G)\geq 3$, then the extendability of $G$ is at least $\lceil \frac{k+3}{2}-\frac{\alpha(G)}{2}\rceil-1 \geq \lceil \frac{k+3}{2}-\frac{v}{2(1+k/(-\theta_v))}\rceil-1$. \end{lemma} \begin{proof} Let $t=\lceil \frac{k+3}{2}-\frac{\alpha(G)}{2}\rceil-1$. Assume that $G$ is not $t$-extendable. By Lemma \ref{notn}, there is a vertex disconnecting set $S$ containing $t$ independent edges, such that $o(G-S)\geq |S|-2t+2\geq k-2t+2\geq 3$. Because $G$ is primitive, Theorem \ref{kconnected} implies that $|S|\geq k+1$. Thus, $\alpha(G)\geq o(G-S)\geq |S|-2t+2\geq k-2t+3$, contradiction with $t=\lceil \frac{k+3}{2}-\frac{\alpha(G)}{2}\rceil-1$. The second part follows from the Hoffman-ratio bound \cite{BH,GR} stating that $\alpha(G)\leq \frac{v}{1+k/(-\theta_v)}$. \end{proof} \begin{lemma}\label{valpha} If $G$ is a $(v,k,\lambda,\mu)$-srg with $\lambda=0$, then $v>3\alpha(G)$ except when $G$ is the Petersen graph. \end{lemma} \begin{proof} The Hoffman-ratio bound \cite{BH,GR} states that $\alpha(G)\leq \frac{v}{1+k/(-\theta_v)}$. As $\theta_2(-\theta_v)=k-\mu 2$, thus $\alpha(G)g(g+3)/2$, which is impossible by Seidel's absolute bound (see \cite[Section 9.1.8]{BH2} or \cite{DGS}). When $\mu=1$, $G$ must be the Petersen graph, where $\alpha(G)=4$ and $v=10\leq 3\alpha(G)=12$. Finally, when $\mu=2$, $G$ is the $(16,5,0,2)$-srg, where $16=v>3\alpha(G)=15$. \end{proof} \begin{lemma}\label{tfsrgedgecut} Let $G$ be a $(v,k,\lambda,\mu)$-srg with $v$ even, $\lambda=0$ and $k\geq 7$. If $A$ is a subset of vertices such that $5\leq |A| \leq v-k-1$ and $|A|$ is odd, then $e(A,A^c)\geq 5k-12$. \end{lemma} \begin{proof} Assume that $5\leq |A| \leq 2k-5$. As $G$ is triangle-free, so is the subgraph induced by $A$. By Tur\'{a}n's Theorem, the number of edges inside $A$ is at most $\frac{|A|^2-1}{4}$. So, $e(A) \leq \frac{|A|^2-1}{4}$ and $e(A,A^c)=k|A|-2e(A) \geq k|A|-\frac{|A|^2-1}{2}$. The minimum is attained at $|A|=5$ or $2k-5$. In either case, we have $e(A,A^c) \geq 5k-12$. Assume that $2k-3 \leq |A| \leq v/2$. We have $e(A, A^c)\geq \frac{(k-\theta_2)|A|(v-|A|)}{v}\geq \frac{(k-\theta_2)(2k-3)}{2}$ (see \cite[Corollary 4.8.4]{BH2} or \cite{Mohar}). Since $\theta_2(-\theta_v)=k-\mu\leq k-1$ and $\theta_v\leq -3$ when $k\geq 7$, we have $\theta_2\leq \frac{k-1}{3}$ and $k-\theta_2\geq \frac{2k+1}{3}$. So, when $k\geq 7$, $k-\theta_2\geq 5$ and $e(A,A^c)\geq \frac{5(2k-3)}{2} >5k-12.$ Assume that $v/2<|A| \leq v-k-1$. It is equivalent to that $k+1 \leq |A^c| k/2$, we get that $v=1+k+k(k-\lambda-1)/\mu<3k-2\lambda-1$. Also, $\mu>k/2$ implies that $G$ has integer eigenvalues and $\theta_2 (-\theta_v)=k-\muk/2$ and $k \geq 8$ is $3$-extendable. \end{corollary} \begin{proof} If $\theta_2 \geq 2$, then $\theta_v=\frac{\mu-k}{\theta_2}>-k/4$ as $\mu>k/2$. Thus, $\lambda=\mu+\theta_2+\theta_v>k/2+2-k/4=k/4+2$. By Theorem \ref{srgn2}, the extendability is at least $\lceil \frac{2k+2\lambda+8}{10}\rceil>\lceil k/4+1.2\rceil\geq 4$ for $k\geq 8$. If $\theta_2=1$, we will show that $\lambda\geq \frac{k-3}{2}$. The second bound in Theorem \ref{srgn2} will then imply the extendability is at least $\lceil \frac{k+1}{4} \rceil\geq 3$. Since $\theta_2=1$, then $-\theta_v=k-\mu, 1+\theta_v=\lambda-\mu$ and consequently, $\lambda=2\mu+1-k$ and $v=1+k+\frac{k(k-\lambda-1)}{\mu}=1+k+\frac{2k(k-\mu-1)}{\mu}$. If $3k/4\leq \mu\frac{k-3}{2}$. Otherwise, assume that $k/2<\mu<3k/4$, and let $f$ be the multiplicity of $\theta_2$ and $g$ be the multiplicity of $\theta_v$. We have $1+f+g=v$ and $k+f+(\mu-k)g=0$ and therefore, $1-k+(k-\mu+1)g=v=1+k+\frac{2k(k-\mu-1)}{\mu}$. Hence, $2(k-1)k=g(k-\mu+1)\mu>g(1+k/4)(3k/4)$ (as $(k-\mu+1)\mu$ attains minimum at $\mu=3k/4$) and $g<\frac{32(k-1)}{3(k+4)}<11$. Thus, $g\leq 10$. By Seidel's absolute bound (see \cite[Section 9.1.8]{BH2} or \cite{DGS}), $v<\frac{g(g+3)}{2}\leq 65$. We checked all the possible parameter sets of strongly regular graphs with $v$ even and $\theta_2=1$ from the list \cite{B2}. All of them have the property that $\lambda\geq \frac{k-3}{2}$, and there is exactly one parameter set which attains the equality. It is the $(28,15,6,10)$ and there are $4$ such strongly regular graphs, the triangular graph $T(8)$ and the three Chang graphs (see Brouwer's list \cite{B2} or \cite[page 123]{BH2}). \end{proof} Note that Chen \cite{C} proved that every $(2t+n-2)$-connected $K_{1,n}$-free graph of even order is $t$-extendable (see also Aldred and Plummer \cite{AP} for extensions of Chen's result). When $\lambda\geq 1$, every $(v,k,\lambda,\mu)$-srg is $k$-connected and $K_{1, \lfloor k/2 \rfloor+1}$-free. If we let $t=\lfloor \frac{1}{2}\lceil \frac{k+2}{2} \rceil \rfloor$ and $n=\lfloor k/2 \rfloor+1$, then Chen's result implies that such strongly regular graph is $\lfloor \frac{1}{2}\lceil \frac{k+2}{2} \rceil \rfloor$-extendable. This is the same as our result when $\theta_2=1$, $\mu >k/2$ and $\lambda\leq \frac{k-3}{2}$. For other cases, our lower bound is better than Chen's result. Note that Chen's bound can be improved if one has a better bound than $k/2$ for the independence number of the first subconstituents of the strongly regular graph. \begin{theorem}\label{srgn} Let $G$ be a primitive $(v,k,\lambda,\mu)$-srg with $v$ even and $\lambda\geq 1$. If $\mu\leq k/2$, then $G$ is $n$-extendable, where $n=\lceil \frac{k^2-k-3}{3k-7}\rceil-1$. %If $k/2<\muk/2$ is similar, the only difference being that we use $\frac{(k-2)[k(k-1)-(k-3)\mu]}{(k-3)\mu+k}$ (from Lemma \ref{Independentset3}) to lower bound $s-a$ in \eqref{ineqsa}. \end{proof} \begin{corollary}\label{3lambda1} Any primitive $(v,k,\lambda,\mu)$-srg with $v$ even, $\lambda \geq 1$ and $k \geq 8$ is $3$-extendable. \end{corollary} \begin{proof} Note that $\lceil \frac{k^2-k-3}{3k-7}\rceil-1=\lfloor k/3\rfloor$ if $k\equiv 0,1\pmod{3}$ and $\lfloor k/3\rfloor+1$, otherwise. Corollary \ref{k8mularge} and Theorem \ref{srgn} imply that any primitive $(v,k,\lambda,\mu)$-srg with $\lambda \geq 1$ and $k \geq 8$ is $3$-extendable. \end{proof} %, except for the cases that $k/2<\muk$ and $\lambda>1$. Thus, $\lambda=2$ and we obtain that $k+1=2\mu$ and $v=1+k+k(k-\lambda-1)/\mu=3k-7+\frac{8}{k+1}$. As $v$ is an integer, $k\in \{1,3,7\}$. But such strongly regular graph does not exist. Thus, any primitive $(v,k,\lambda,\mu)$-srg with $\lambda \geq 1$ and $k \geq 8$ is $3$-extendable. \begin{theorem}\label{3trianglefree} Any primitive $(v,k,\lambda,\mu)$-srg with $v$ even, $\lambda=0$ and $k \geq 8$ is $3$-extendable. \end{theorem} \begin{proof} We show that $G$ is $3$-extendable by contradiction. Assume that $G$ is not $3$-extendable. Lemma \ref{notn} implies that $G$ has a vertex subset $S$, such that $S$ contains $3$ independent edges, and $o(G-S)\geq |S|-4$. Let $S$ be such disconnecting set with maximum size. We first claim that any non-singleton component of $G-S$ cannot induce a bipartite graph. If that was the case, the respective component would have two partitions $X$ and $Y$. Assume that $|X|>|Y|$, then define $S^\prime=S\cup Y$. Then $|S^\prime|>|S|$ and $o(G-S')\geq |S'|-4$, contradicting the maximality of $|S|$. Note that $G-S$ cannot contain exactly 3 vertices, because $G$ is triangle free and any component with 3 vertices must be a path, which is bipartite. By similar argument, $G-S$ contains no even components. If it contains a even component, we can put one vertex of this even component into $S$, which make $|S|$ larger and $S$ still satisfy $o(G-S)\geq |S|-4$. But it contradicts to the maximality of $|S|$. Let $O_1, O_2, \dots, O_r$ be all the odd components of $G-S$. If $G-S$ has only singleton components, then $\alpha(G)\geq o(G-S) \geq |S|-4\geq v-\alpha(G)-4$. Thus, $3\alpha(G)K^2$ or $K\geq 5$ and $n>4K^2+5K+24+\frac{96}{K-4}$, the extendability of $G$ is $\lceil k/2\rceil -1$, where $k$ is the valency of $G$. \end{theorem} \begin{proof} Let $G$ be the block graph of a Steiner $K$-system, and let $B$ denote the block sets of the 2-$(n,K,1)$ design. Consider the neighborhood $N(\{1,\ldots, K\})$ of the vertex $\{1,2, \ldots, K\}$. There is a partition of $N(\{1,\ldots, K\})$ into cliques, which is $A_i=\big\{b\in B \mid b\cap \{1,2, \ldots, K\}=\{i\}\big\}$ for $1\leq i \leq K$. For any $A_i$ and $A_j$, there exist $b_i\in A_i$ and $b_j\in A_j$ such that $n\in b_i$ and $n \in b_j$. So, $b_i$ and $b_j$ are adjacent. The graph obtained by contracting each $A_i$ is a complete graph. By Lemma \ref{N(x)}, the first subconstituent $\Gamma_1(x)$ contains a perfect matching or a near perfect matching. There are $\lceil k/2 \rceil$ independent edges incident with all $N(x)$ and not incident with $x$. This implies $G$ is not $\lceil k/2\rceil$-extendable. Assume that $G$ is not $(\lceil k/2\rceil -1)$-extendable. By Lemma \ref{notn}, there is a subset of vertices $S$ such that $S$ contains $\lceil k/2\rceil -1$ independent edges and $r=o(G-S)\geq |S|-2(\lceil k/2\rceil -1)+2$. Let $O_1, O_2, \ldots, O_r$ be all the odd components of $G-S$, and $P_i$ denote the union of the blocks corresponding to the vertices of $O_i$, where $1\leq i \leq r$. Since $|P_i|\geq K$ and $P_i\cap P_j=\emptyset$ for $i\neq j$, we have that $n\geq |P_1|+ |P_2|+ \ldots+ |P_r|\geq Kr$. If $r\leq 2$, then as $|S|\geq k$ by Theorem \ref{kconnected}, we get that $2\geq o(G-S)\geq |S|-2(\lceil k/2\rceil -1)+2\geq k-2\lceil k/2 \rceil +4 \geq 3$, contradiction. Otherwise, if $r\geq 3$ and there exists two singleton components among $O_1,\dots,O_r$, then $|S| \geq 2k-\mu$. This implies that $n/K\geq r\geq |S|-2(\lceil k/2\rceil -1)+2\geq 2k-\mu-2\lceil k/2 \rceil +4\geq k-\mu+3=\frac{K(n-K)}{K-1}-K^2+3$, contradiction with $K\in \{3,4\}$ and $n>K^2$, or $K\geq 5$ and $n>4K^2+5K+24+\frac{96}{K-4}$. Otherwise, if there is at most one singleton component, then there are at least two non-singleton odd components, say $O_1, O_2$. By the results in \cite[Section 3]{CKL}, $|S|\geq |N(O_1)|\geq 2k-\lambda-2$. As before, $n/K\geq r\geq |S|-2(\lceil k/2\rceil -1)+2 \geq 2k-\lambda-2-2\lceil k/2\rceil +4\geq k-\lambda +1 =\frac{K(n-K)}{K-1}-(K-1)^2-\frac{n-1}{K-1}+3=n-K^2+K+1$, contradiction. \end{proof} Note that when $K\in \{3,4\}$ and $n\leq K^2$, the block graph of Steiner $K$-system is either a complete graph or a complete multipartite graph. If $v=\frac{n(n-1)}{K(K-1)}$ is odd, then $k=\frac{K(n-K)}{K-1}$ must be even. The proof of the next result is similar to the proof of Theorem \ref{design} and will be omitted. \begin{theorem}\label{designodd} Let $G$ be the block graph of a Steiner $K$-system on $n$ points such that $\frac{n(n-1)}{K(K-1)}$ is odd. If $K\in \{3,4\}$ and $n>K^2$ or $K\geq 5$ and $n>4K^2+5K+24+\frac{96}{K-4}$, the semi-extendability of $G$ is $k/2-1$, where $k$ is the valency of $G$. \end{theorem} \subsection{Latin square graphs} An orthogonal array $OA(t,n)$ with parameters $t$ and $n$ is a $t\times n^2$ matrix with entries from the set $[n]=\{1,\dots,n\}$ such that the $n^2$ ordered pairs defined by any two distinct rows of the matrix are all distinct. It is known that an orthogonal array $OA(t,n)$ is equivalent to the existence of $t-2$ mutually orthogonal Latin squares. Given an orthogonal array $OA(t,n)$, one can define a graph $G$ as follows. The vertices of $G$ are the $n^2$ columns of the orthogonal array and two distinct columns are adjacent if they have the same entry in one coordinate position. The graph $G$ is an $(n^2, t(n-1), n-2+(t-1)(t-2), t(t-1))$-srg. Any strongly regular graph with such parameters is called a Latin square graph (see \cite[Section 9.1.12]{BH}, \cite[Section 10.4]{GR} or \cite[Chapter 30]{VanLintWilson}). When $t=2$ and $n\neq 4$, such a graph must be the line graph of $K_{n,n}$ which is also the graph associated with an orthogonal array $OA(2,n)$ (see \cite[page 123]{BH2}) \begin{theorem}\label{OA} Let $n$ and $t$ be two integers such that $n$ is even and $n\geq 2t\geq 6$. If $G$ is a Latin square graph corresponding to an $OA(t,n)$, then the extendability of $G$ is $\lceil k/2\rceil -1$, where $k$ is the valency of $G$. \end{theorem} \begin{proof} Let $C$ denote the column set of the orthogonal array $OA(t,n)$ corresponding to $G$. Consider the neighborhood $N(c_1)$ of a column $c_1=(c_1(1), \ldots, c_1(t))^T$ of $C$. There is a partition of $N(c_1)$ into cliques, which is $A_i=\{c \in C \mid c(i)=c_1(i)\}$ for $1\leq i \leq t$. Let $l\in [n]$ such that $l\not = c_1(3)$. There exist $c \in A_1$ such that $c(3)=l$ and there is $c^\prime \in A_2$ such that $c^\prime(3)=l$. Thus $c$ and $c^\prime$ are adjacent. The graph obtained by contracting each $A_i$ is a complete graph. By Lemma \ref{N(x)} and the same argument in Theorem \ref{design}, we deduce that $G$ is not $\lceil k/2\rceil$-extendable. Assume that $G$ is not $(\lceil k/2\rceil -1)$-extendable. By Lemma \ref{notn}, there is a subset of vertices $S$ such that $S$ contains $\lceil k/2\rceil -1$ independent edges and $r=o(G-S)\geq |S|-2(\lceil k/2\rceil -1)+2$. Let $O_1, O_2, \ldots, O_r$ be all the odd components of $G-S$. If $r\leq 2$, then as $|S|\geq k$ by Theorem \ref{kconnected}, we have $2\geq r\geq |S|-2(\lceil k/2\rceil -1)+2\geq k-2\lceil k/2 \rceil +4 \geq 3$, contradiction. Otherwise, if $r\geq 3$ and there exists two singleton components among $O_1,\dots,O_r$, then $|S|\geq 2k-\mu$. Because $\alpha(G)\leq n$, we deduce that $n\geq r\geq |S|-2(\lceil k/2\rceil -1)+2\geq 2k-\mu-2\lceil k/2 \rceil +4\geq k-\mu+3=t(n-1)-t(t-1)+3=t(n-t)+3\geq 2(n-2)+3$. Thus, $n\leq 1$, contradiction. If $r\geq 3$ and there is at most one singleton component, then there are at least two non-singleton odd components, say $O_1, O_2$. By the results in \cite[Section 4]{CKL}, $|N(O_1)|\geq 2k-\lambda -2$. Thus $|S| \geq 2k-\lambda -2$. As before, $n\geq o(G-S)\geq k-\lambda+1=t(n-1)-n+2-(t-1)(t-2)+1=(t-1)(n-t+1)+2\geq n+1$, contradiction. \end{proof} The proof of our next result is similar and will be omitted. \begin{theorem}\label{OAodd} Let $n$ and $t$ be two integers such that $n$ is odd and $n\geq 2t\geq 6$. If $G$ is a Latin square graph corresponding to an $OA(t,n)$, then the semi-extendability of $G$ is $k/2-1$, where $k$ is the valency of $G$. \end{theorem} The line graph of $K_{n,n}$ is a $(n^2, 2(n-1),n-2,2)$-srg. It can be regarded as a strongly regular graph corresponding to an $OA(2,n)$. \begin{theorem}\label{line} Let $n$ be an even integer such that $n\geq 4$. If $G$ is the line graph of $K_{n,n}$, the extendability of $G$ is $k/2=n-1$. \end{theorem} \begin{proof} The first subconstituent $\Gamma_1(x)$ of some vertex $x$ of $G$ is the disjoint union of two cliques of odd order. Pick two vertices $y$ and $z$ that are not adjacent to $x$. If $S=N(x)\cup \{y,z\}$, then $S$ contains a matching of size $n$ that is not contained in any perfect matching. Therefore, $G$ is not $n$-extendable. Assume that $G$ is not $k/2$-extendable. By Lemma \ref{notn}, there is a subset of vertices $S$ such that $S$ contains $k/2$ independent edges (therefore, $S$ is not the neighborhood of some vertex) and $r=o(G-S)\geq |S|-2(k/2)+2$. Let $O_1, O_2, \ldots, O_r$ be all the odd components of $G-S$. If $r\leq 2$, then as $S$ is not the neighborhood of some vertex, by Theorem \ref{kconnected} $|S|\geq k+1$ and therefore, $2\geq r \geq |S|-k+2\geq 3$, contradiction. If $r\geq 3$, the proof is the same as Theorem \ref{OA} except for the case when there is at most one singleton component among $O_1,\dots,O_r$. In this case, we need to show that $o(G-S)\leq n-1$. This inequality can be proved by contradiction. We know that $o(G-S)\leq \alpha(G)=n$. If $o(G-S)=n$, then we can pick a vertex $x_i$ from each component $O_i$ and $I=\{x_1, \dots, x_n\}$ will form an independent set of size $n$. The set $I$ can be regarded as a perfect matching in $K_{n,n}$. Any edge in $K_{n,n}$ outside this perfect matching will have non-empty intersection with two edges of this perfect matching. Hence, any vertex in the line graph of $K_{n,n}$ but not in $I$ will be adjacent with two vertices in $I$. If $O_1$ is not a singleton, then there is a vertex $y \in O_1$, where $y\neq x_1$ and $y$ is adjacent to $x_i$ for some $i\neq 1$. This contradicts the fact that $O_1$ and $O_i$ are two distinct components in $G-S$. \end{proof} \begin{theorem}\label{lineodd} Let $n$ be an odd integer such that $n\geq 3$. If $G$ is the line graph of $K_{n,n}$, the semi-extendability of $G$ is $k/2-1=n-2$. \end{theorem} \begin{proof} The first subconstituent $\Gamma_1(x)$ of some vertex $x$ of $G$ is the disjoint union of two cliques of even order. Thus, $\Gamma_1(x)$ contains a matching of size $n-1$ and this will imply that $G$ is not $(n-1)$-semi-extendable. The proof that $G$ is $(n-2)$-semi-extendable is similar to the proof of Theorem \ref{line} and will be omitted. \end{proof} \subsection{The extendability of the known triangle-free strongly regular graphs}\label{trianglefreesrg} We determine the extendability or semi-extendability of the known primitive triangle-free strongly regular graphs. There are seven known examples of such graphs and they have parameter sets: $(5,2,0,1)$, $(10, 3, 0,1)$, $(16,5,0,2)$, $(50,7,0,1)$, $(56,10,0,2)$, $(77,16,0,4)$, $(100,22,0,6)$. We first discuss the known triangle-free strongly regular graphs of even order. Lou and Zhu \cite{LZ} proved that the extendability of the $(10,3,0,1)$-srg (the Petersen graph) is $1$. The $(16,5,0,2)$-srg is called the folded $5$-cube as it can be obtained from the $5$-dimensional cube on $32$ vertices by identifying antipodal vertices. The $(16,5,0,2)$-srg is known as the complement of the Clebsch graph (see \cite[page 117]{BH2}) or as the Clebsch graph (see \cite[Example 21.4, page 263]{VanLintWilson}). \begin{theorem} \label{fold} The folded $5$-cube is precisely $3$-extendable. \end{theorem} \begin{proof} Let $G$ be the $(16,5,0,2)$-srg. We first show that $G$ is not $4$-extendable. Let $x$ be a vertex of $G$. It is known that the second subconstituent $\Gamma_2(x)$ of $x$ is isomorphic to the Petersen graph. Consider four independent edges of $\Gamma_2(x)$. We claim that these four edges are not contained in a perfect matching of $G$. Let $S$ be the complement of the neighborhood of $x$ in $G$. Then $S$ contains four independent edges and $5=o(G-S)\geq |S|-2\cdot 4+2=5$. Lemma \ref{notn} implies that $G$ is not 4-extendable. We show that $G$ is $3$-extendable by contradiction. Assume that $G$ is not $3$-extendable. Lemma \ref{notn} implies that $G$ has a vertex subset $S$, such that $S$ contains $3$ independent edges, and $o(G-S)\geq |S|-4$. Let $S$ be such disconnecting set with maximum size. By the same argument in the proof of Theorem \ref{3trianglefree}, any non-singleton component of $G-S$ cannot contain exactly $3$ vertices. If $G-S$ has no singleton components, then $G-S$ has at most two odd components (since $\alpha(G)=5$ and each non-singleton component has two non-adjacent vertices). Thus, $|S| \leq o(G-S)+4\leq 6$. Lemma \ref{Haemers} implies that $ |S|\geq 25/2$, a contradiction. If $G-S$ has one or two singleton components, then $G-S$ has at most three odd components. Thus, $|S|\leq o(G-S)+4\leq 7$. However, $S$ contain the neighborhood of a vertex, which is an independent set of size 5. Since $S$ also contains three independent edges, $|S| \geq 8$, contradiction. The remaining case is when $G-S$ has at least three singleton components, say $x, y, z$. As $o(G-S)\leq 5$, $|S|\leq o(G-S)+4\leq 9$. However, $|N(\{x,y,z\})|= 10$. This is because $y, z$ are contained in $\Gamma_2(x)$ which is isomorphic to the Petersen graph. Because $y$ and $z$ are not adjacent, they have one common neighbor in $\Gamma_2(x)$. Hence, there are five vertices adjacent to $y$ or $z$ in $\Gamma_2(x)$. Thus, $|S|\geq |N(\{x,y,z\} )|=10$, contradiction. \end{proof} The $(50,7,0,1)$-srg is called the Hoffman-Singleton graph and its independence number is $15$ (see \cite[Section 13.1]{BCN} or \cite[page 117]{BH2}). \begin{theorem}\label{HS} The Hoffman-Singleton graph is precisely $5$-extendable. \end{theorem} \begin{proof} Let $G$ be the $(50,7,0,1)$-srg. We first show that $G$ is not $6$-extendable. Let $x$ and $y$ be two non-adjacent vertices of $G$ and let $S=N(x)\cup N(y)$. Then $|S|=13$ and $S$ contains $6$ independent edges. Since the second subconstituent $\Gamma_2(x)$ of $x$ is a distance-regular graph with intersection array $\{6,5,1;1,1,6\}$, Lemma \ref{1connected} implies that the subgraph of $\Gamma_2(x)$ obtained by removing the neighbors of $y$ in $\Gamma_2(x)$, has exactly two odd components. Hence, $3=o(G-S)\geq 3=|S|-2\cdot 6+2$. By Lemma \ref{notn}, $G$ is not 6-extendable. We show that $G$ is $5$-extendable by contradiction. Assume that $G$ is not $5$-extendable. By Lemma \ref{notn}, there exists a subset of vertices $S$ such that $S$ contains five independent edges and $o(G-S)\geq |S|-8$. Consider such a set $S$ of maximum size. By the same argument as in the proof of Theorem \ref{3trianglefree}, the maximality of $|S|$ implies that any non-singleton odd component of $G-S$ cannot be bipartite. We use this observation to prove that any non-singleton odd component must has at least $7$ vertices. Assume that $C$ is a non-singleton component with 5 vertices (Otherwise, $C$ induces a bipartite graph). Then $C$ must induce a cycle on $5$ vertices. Thus, $o(G-S) \leq \alpha (G)-1=14$ and $|S|\leq o(G-S)+8\leq 22 $. However, $|N(C)|=25$ because each vertex in $C$ has 5 neighbors in $S$, and any two vertices in $C$ have no common neighbors in $S$. Thus, $22\geq |S|\geq |N(C)|\geq 25$, a contradiction. Thus, any odd non-singleton component of $G-S$ has at least $7$ vertices. If $G-S$ has at least $2$ non-singleton odd components, then $o(G-S)\leq 11$, and $|S| \leq o(G-S)+8\leq 19$. Lemma \ref{Haemers} implies that $|S|\geq \frac{4\times 7\times (50-19-7)}{25}>26$, a contradiction. If $G-S$ has exactly one non-singleton odd component, then $o(G-S)\leq 13$ and $|S| \leq o(G-S)+8\leq 21$. If $G-S$ contains at least $7$ singleton components, then Lemma \ref{Haemers} implies that $ |S|\geq \frac{4\times 7\times (50-21-7)}{25}>24$, a contradiction. If $G-S$ contains between $3$ and $6$ singleton components, then $|S|\leq o(G-S)+8\leq 15$. However, for any three independent vertices $x,y,z$, $|N(x)\cup N(y)\cup N(z)| \geq 3\cdot 7-{3\choose 2}\cdot 1=18$, a contradiction. If $G-S$ has one or two singleton components, then $|S|\leq o(G-S)+8\leq 11$. Since $S$ contains the neighborhood $N(x)$ of a vertex $x$ and $S$ contains 5 independent edges, $S$ must contain another 5 vertices outside of $N(x)$. Thus, $|S|\geq 12$, a contradiction. If $G-S$ only has singleton odd components, then $G-S$ has no even components. Otherwise, we can put one vertex of the even components into $S$. In this way, $|S|$ will increase by one, and $o(G-S)$ will increase at least by one, contradicting the maximality of $|S|$. Thus, $|S|=50-o(G-S)\geq 35$ contradicting the inequality $|S|\leq o(G-S)+10\leq 25$. \end{proof} The $(56,10,0,2)$-srg is known as the Gewirtz graph or the Sims-Gewirtz graph and its independence number is $16$ (see \cite[page 372]{BCN} or \cite[page 117]{BH2}). \begin{theorem} The Gewirtz graph is precisely $8$-extendable. \end{theorem} \begin{proof} Let $G$ be the Gewirtz graph. We first show that $G$ is not $9$-extendable. Let $x$ and $y$ be two non-adjacent vertices of $G$. Because every vertex in $N(x)\setminus N(y)$ has exactly $2$ neighbors in $N(y)\setminus N(x)$ and every vertex in $N(y)\setminus N(x)$ has exactly $2$ neighbors in $N(x)\setminus N(y)$, we can find $8$ independent edges with one endpoint in $N(x)\setminus N(y)$ and the other endpoint in $N(y)\setminus N(x)$. Let $z\in N(x)\cap N(y)$ and let $w$ be a neighbor of $z$ that is not $x$ nor $y$. Let $S=N(x)\cup N(y)\cup \{w\}$. It follows that $S$ contains $9$ independent edges, $|S|=19$ and $o(G-S)\geq 3$. Thus, $o(G-S)\geq 3=|S|-16$ and by Lemma \ref{notn}, $G$ is not 9-extendable. Assume $G$ is not $8$-extendable. Lemma \ref{notn} implies the existence of subset of vertices $S$ such that $S$ contains $8$ independent edges, and $o(G-S)\geq |S|-14$. Take such a set $S$ of maximum size. By a similar argument as before, any non-singleton odd component of $G-S$ must have at least $7$ vertices. Assume that $C$ is a non-singleton component with 5 vertices. If $C$ has no odd cycles, then $C$ is a bipartite graph and we can add two vertices of $C$ to $S$. Then $|S|$ will increase by $2$ and $o(G-S)$ will increase by $2$, contradicting the maximality of $S$. If $C$ induces a pentagon, then $o(G-S) \leq \alpha (G)-1=15$ and, $|S|\leq o(G-S)+14\leq 29 $. However, $|N(C)|=8\times5-5=35$, a contradiction. Thus, any non-singleton component should have size at least $7$. If $G-S$ has at least $2$ non-singleton odd components, then $o(G-S)\leq 12$, and $|S| \leq o(G-S)+14\leq 26$. Lemma \ref{Haemers} implies that $|S|\geq \frac{2\times 7\times (56-26-7)}{9}=\frac{322}{9}=35.77>35$, a contradiction. If $G-S$ has exactly one non-singleton odd component, then $o(G-S)\leq 14$, and $|S| \leq o(G-S)+14\leq 28$. Let $t$ be the number of singleton components. If $t\geq 7$, then Lemma \ref{Haemers} implies that $|S|\geq \frac{2\times 7\times (56-28-7)}{9}=\frac{98}{3}=32.66>32$, a contradiction. If $3\leq t \leq 6$, then $|S|-14\leq o(G-S)= 7$. Thus, $|S|\leq 21$. However, for any three independent vertices $x,y$ and $z$, $|S|\geq |N(x)\cup N(y)\cup N(z)| \geq 10\times 3-6=24$, a contradiction. If $1\leq t \leq 2$, then $|S|-14\leq o(G-S)\leq 3$. Thus, $|S| \leq 17$. Since $S$ contains the neighborhood of a vertex, which is an independent set, in order for $S$ to contain 8 independent edges, $S$ must contain another $8$ vertices. Thus, $|S|\geq 18$, a contradiction. If $G-S$ only has singleton components. Then $G-S$ has no even components. Otherwise, we can put one vertex of an even components into $S$. In this way, $|S|$ will increase by one, and $o(G-S)$ will increase at least by one, contradicting the maximality of $|S|$. Thus, $|S|=56-o(G-S)\geq 40$, contradicting $|S|\leq o(G-S)+14\leq 30$. \end{proof} The $(100,22,0,6)$-srg is called Higman-Sims graph and its independence number is $22$ (see \cite[Section 3.5 and Section 9.1.7]{BH2}). \begin{theorem} The Higman-Sims graph is precisely $20$-extendable. \end{theorem} \begin{proof} Let $G$ denote the Higman-Sims graph. Let $x$ and $y$ be two non-adjacent vertices. Because every vertex in $N(x)\setminus N(y)$ has exactly $6$ neighbors in $N(y)\setminus N(x)$ and every vertex in $N(y)\setminus N(x)$ has exactly $6$ neighbors in $N(x)\setminus N(y)$, we can find $16$ independent edges with one endpoint in $N(x)\setminus N(y)$ and the other endpoint in $N(y)\setminus N(x)$. Every vertex from $N(x)\cap N(y)$ has exactly $21$ neighbors in the second subconstituent of $x$. Each vertex in the second subconstituent of $x$ has $16$ neighbors in $N(x)\cap N(y)$. By Hall's Marriage Theorem, we can find five independent edges $w_iu_i$ such that $u_i\in N_2(x)$ and $w_i\in N(x)\cap N(y)$ for $1\leq i\leq 5$. Let $S=N(x)\cup N(y)\cup \{w_1, w_2, w_3. w_4, w_5\}$. It follows that $S$ contains $21$ independent edges, $|S|=43$ and $o(G-S)\geq 3=|S|-21\times 2+2$. Lemma \ref{notn} implies that $G$ is not $21$-extendable. If $G$ were not $20$-extendable, by Lemma \ref{notn}, there is a subset of vertices $S$ such that $S$ contains $20$ independent edges and $o(G-S)\geq |S|-38$. As before, we may assume that $S$ is such a disconnecting set with maximum size. Then any non-singleton odd component of $G-S$ has at least $5$ vertices. Furthermore, we can prove that any non-singleton odd component has at least $7$ vertices. Assume that $C$ is a non-singleton component with $5$ vertices. If $C$ has no odd cycle, then $C$ is bipartite graph and we can add two vertices from the same color class of $C$ into $S$. Then $|S|$ will increase by $2$ and $o(G-S)$ will increase by $2$, contradicting the maximality of $|S|$. If $C$ induces a pentagon, then $|S|\geq |N(C)|=20\times 5-5 \times 5=75$. However, since $o(G-S) \leq \alpha (G)-1=21$, we get that $|S|\leq o(G-S)+38\leq 59$, a contradiction. Note that any non-singleton odd component of $G-S$ contains an independent set of order $3$. If $G-S$ has at least two non-singleton odd components, then $o(G-S)\leq 18$, and $|S| \leq o(G-S)+38\leq 56$. However, by Lemma \ref{Haemers}, $|S|\geq \frac{6\times 7\times (100-56-7)}{25}>62$, contradiction. If $G-S$ has exactly one non-singleton odd component, then $o(G-S)\leq 20$, and $|S| \leq o(G-S)+38\leq 58$. Let $t$ be the number of singleton components. If $t\geq 7$, then Lemma \ref{Haemers} implies that $|S|\geq \frac{6\times 7\times (100-58-7)}{25}>58$, a contradiction. If $3\leq t \leq 6$, then $|S|\leq o(G-S)+38=45$. However, for any three independent vertices $x, y$ and $z$ from $G-S$, $|S|\geq |N(x)\cup N(y)\cup N(z)| \geq 22\times 3-3\times6=48$, a contradiction. If $1\leq t \leq 2$, then $|S|\leq o(G-S)+38\leq 41$. Since $S$ contains the neighborhood of a vertex, which is an independent set, in order for $S$ to contain 20 independent edges, $S$ must contain another $20$ vertices. Thus, $|S|\geq 42$, a contradiction. If $G-S$ only has singleton odd components, then $G-S$ has no even components. Otherwise, we can put one vertex of an even components into $S$. In this way, $|S|$ will increase by one, and $o(G-S)$ will increase at least by one, contradicting the maximality of $|S|$. Thus, $|S|=100-o(G-S)\geq 78$ which contradicts with $|S|\leq o(G-S)+38\leq 60$. \end{proof} We also determine the semi-extendability of the known triangle-free strongly regular graphs with odd order. The $(5,2,0,1)$-srg is precisely $0$-semi-extendable. The only other known triangle-free strongly regular graph of odd order is the $M_{22}$ graph which is $(77,16,0,4)$-srg with independence number $21$ (see \cite[page 118]{BH2}). \begin{theorem} The $M_{22}$ graph is precisely $13$-semi-extendable. \end{theorem} \begin{proof} Let $G$ denote the $M_{22}$ graph. Let $x$ and $y$ be two non-adjacent vertices. Because every vertex in $N(x)\setminus N(y)$ has exactly $4$ neighbors in $N(y)\setminus N(x)$ and every vertex in $N(y)\setminus N(x)$ has exactly $4$ neighbors in $N(x)\setminus N(y)$, we can find $12$ independent edges with one endpoint in $N(x)\setminus N(y)$ and the other endpoint in $N(y)\setminus N(x)$. Every vertex from $N(x)\cap N(y)$ has exactly $14$ neighbors in the second subconstituent of $x$. We can find two independent edges $w_iu_i$ such that $u_i$ is in the second subconstituent of $x$ and $w_i\in N(x)\cap N(y)$ for $1\leq i\leq 2$. Let $S=N(x)\cup N(y)\cup \{w_1, w_2\}$. It follows that $S$ contains $14$ independent edges, $|S|=30\geq 29$ and $o(G-S)\geq 3=|S|-14\times 2+1$. Lemma \ref{notn1/2} implies that $G$ is not $14$-semi-extendable. If $G$ were not $13$-semi-extendable, by Lemma \ref{notn1/2}, there is a subset of vertices $S$ such that $|S|\geq 27$ and $S$ contains $13$ independent edges and $o(G-S)\geq |S|-25$. As before, we may assume that $S$ is such a disconnecting set with maximum size. Then any non-singleton odd component of $G-S$ has at least $5$ vertices. Furthermore, we can prove that any non-singleton odd component has at least $7$ vertices. Assume that $C$ is a non-singleton component with $5$ vertices. If $C$ has no odd cycle, then $C$ is bipartite graph and we can add two vertices from the same color class of $C$ into $S$. Then $|S|$ will increase by $2$ and $o(G-S)$ will increase by $2$, contradicting the maximality of $|S|$. If $C$ induces a pentagon, then $|S|\geq |N(C)|=14\times 5- 3\times 5=55$. However, since $o(G-S) \leq \alpha (G)-1\leq 20$, we get that $|S|\leq o(G-S)+25\leq 45$, a contradiction. Note that any non-singleton odd component of $G-S$ contains an independent set of order $3$. If $G-S$ has at least two non-singleton odd components, then $o(G-S)\leq 17$, and $|S| \leq o(G-S)+25\leq 42$. However, by Lemma \ref{Haemers}, $|S|\geq \frac{ 7\times (77-42-7)}{4}=49$, contradiction. If $G-S$ has exactly one non-singleton odd component, then $o(G-S)\leq 19$, and $|S| \leq o(G-S)+25\leq 44$. Let $t$ be the number of singleton components. If $t\geq 7$, then Lemma \ref{Haemers} implies that $|S|\geq \frac{ 7\times (77-42-7)}{4}=49$, a contradiction. If $3\leq t \leq 6$, then $|S|\leq o(G-S)+25\leq 32$. However, for any three independent vertices $x, y$ and $z$ from $G-S$, $|S|\geq |N(x)\cup N(y)\cup N(z)| \geq 16\times 3-3\times4=36$, a contradiction. If $1\leq t \leq 2$, then $|S|\leq o(G-S)+25\leq 27$. Since $S$ contains the neighborhood of a vertex, which is an independent set, in order for $S$ to contain 13 independent edges, $S$ must contain another $13$ vertices. Thus, $|S|\geq 29$, a contradiction. If $t=0$, then $o(G-S)=1$. It is also impossible since by our assumption $o(G-S)\geq |S|-25 \geq 2$. If $G-S$ only has singleton odd components, then $G-S$ has no even components. Otherwise, we can put one vertex of an even components into $S$. In this way, $|S|$ will increase by one, and $o(G-S)$ will increase at least by one, contradicting the maximality of $|S|$. Thus, $|S|=77-o(G-S)\geq 56$ which contradicts with $|S|\leq o(G-S)+25\leq 46$. \end{proof} \section{Final Remarks} The extendability of a strongly regular graph is not determined by its parameters. The Shrikhande graph and the line graph of $K_{4,4}$ both have parameter set $(16,6,2,2)$. The extendability of the Shrikhande graph is $2$ and the extendability of $L(K_{4,4})$ is $3$. However, we find it remarkable that the extendability of every known primitive triangle-free strongly regular graph of valency $k$ and even order, equals $k-2$. We make the following conjecture regarding the extendability properties of strongly regular graphs of valency $k$. \begin{conjecture} If $G$ is a primitive strongly regular graph of valency $k$, then its extendability (or semi-extendability) is at least $\lceil k/2\rceil -1$. \end{conjecture} Note that this conjecture is not true for imprimitive strongly regular graph. For example, the extendability of $K_{a\times 3}$ is $a/2=k/4$. The conjecture above would be essentially best possible since there are many strongly regular graphs of valency $k$ that are not $\lceil k/2\rceil$-extendable. If $\Gamma$ is a $(v,k,\lambda,\mu)$-srg with $\lambda>\theta_2$, then the first subconstituent $\Gamma_1(x)$ of any vertex $x$ is connected by eigenvalue interlacing. If $G$ is not a conference graph, then $\lambda-\theta_2\geq 1$ as $\theta_2$ is an integer. The first subconstituent $\Gamma_1(x)$ is $\lambda$-regular with second largest eigenvalue at most $\theta_2$. By \cite{CGH}, $\Gamma_1(x)$ contains a matching of size $\lfloor k/2\rfloor$. If $k$ is even, then this matching cannot be extended to a maximum matching of $G$. If $k$ is odd, one can add one disjoint edge to this matching such that the result matching of size $\lceil \frac{k}{2}\rceil$ cannot be extended to a maximum matching of $G$. If $G$ is a conference graph with parameters $(4t+1,2t,t-1,t)$-srg, $\lambda-\theta_2>1$ when $t\geq 4$. If $t=2$ or $t=3$, then the first subconstituent contains a matching of size $t$ that cannot be extended to a maximum matching of $G$. We also remark that there are strongly regular graphs $\Gamma$ such that the first subconstituent $\Gamma_1(x)$ does not contain a matching of size $\lfloor k/2\rfloor$ for any vertex $x$. For example, if $\Gamma_1(x)$ is a disjoint union of cliques $K_{\lambda+1}$ and $\lambda$ is even, then $\Gamma_1(x)$ will not contain a matching of size $\lfloor k/2 \rfloor$. It would be nice to use the extendability properties of strongly regular graphs to study the edge-chromatic number of such graphs of even order. Results from \cite{BH,CGH} imply that any $k$-regular graph with second largest eigenvalue $\theta_2$ contains at least $(k-\theta_2)/2$ edge disjoint perfect matchings. It would be interesting to improve this bound for strongly regular graphs. Counting perfect matchings in regular graphs is an important problem in discrete mathematics (see \cite{F, LP}) and a well-known conjecture (see \cite[Conjecture 8.18]{LP}) states that for any $k\geq 3$, there exists positive constants $c_1(k)$ and $c_2(k)$ such that any $k$-regular $1$-extendable graph of order $v$ contains at least $c_2(k)c_1(k)^v$ perfect matchings (also $c_1(k)\rightarrow \infty$ as $k\rightarrow \infty$). Seymour (see \cite{EKKKN}) showed that $k$-regular $(k-1)$-edge-connected graphs of order $v$ contains at least $2^{(1-1/k)(1-2/k)v/3656}$ perfect matchings. It would be nice to improve these estimate for strongly regular graphs. Investigating the extendability properties of distance-regular graphs is also an interesting problem that we leave for a future work. One can deduce from the work of Brouwer and Koolen \cite{BK} and Plesn\'{i}k \cite{Plesnik} that every distance-regular graph of even order is $1$-extendable, but it is quite possible that the extendability of many distance-regular graphs is much larger. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Acknowledgements} The authors are grateful to Chris Godsil, Edwin van Dam, Jack Koolen, Ian Wanless and the two anonymous referees for several useful comments and suggestions that have greatly improved our paper. \begin{thebibliography}{99} \bibitem {AHL} R.E.L. Aldred, D.A. Holton and D. Lou, $n$-extendability of symmetric graphs, {\em J. Graph Theory} {\bf 17} (1993), 253--261. \bibitem {AP} R.E.L. Aldred and M.D. Plummer, On matching extensions with prescribed and proscribed edge sets. II, 16th British Combinatorial Conference (London, 1997). {\em Discrete Math.} {\bf 197/198} (1999), 29--40. \bibitem{B} A. E. Brouwer, The uniqueness of the strongly regular graph on 77 points, {\em J. Graph Theory} \textbf{7} (1983), 455--461. \bibitem{B2} A.E. Brouwer, Parameters of Strongly Regular Graphs, list available at http://www.win.tue.nl/$\sim$aeb/graphs/srg/srgtab.html. \bibitem{BCN} A.E. Brouwer, A.M. Cohen and A. Neumaier, {\em Distance-Regular Graphs}, Springer, Heidelberg, 1989. \bibitem{BH} A.E. Brouwer and W.H. Haemers, Eigenvalue and perfect matchings, \emph{Linear Algebra and its Applications} \textbf{395} (2005), 155-162. \bibitem {BH2} A.E. Brouwer and W.H. Haemers, {\em Spectra of Graphs}, Springer Universitext 2012, 250pp monograph. \bibitem {BK} A.E. Brouwer and J.H. Koolen, The vertex-connectivity of a distance-regular graph, {\em European J. Combinatorics} {\bf 30} (2009), 668--673. \bibitem {BL} A.E. Brouwer and J.H. van Lint, Strongly regular graphs and and partial geometries, in {\em Enumeration and design} (Waterloo, Ont., 1982), 85--122, Academic Press, Toronto, ON, 1984. \bibitem{BM} A.E. Brouwer and D.M. Mesner, The connectivity for strongly regular graphs, \emph{European J. Combinatorics} \textbf{6} (1985), 215--216. \bibitem {Cam} P.J. Cameron, Strongly regular graphs, in {\em Topics in Algebraic Graph Theory} (ed. L. W. Beineke and R. J. Wilson), Cambridge Univ. Press, Cambridge, 2004 (ISBN 0521801974), pp. 203--221. \bibitem {Cam2} P.J. Cameron, Random strongly regular graphs?, EuroComb'01 (Barcelona). {\em Discrete Math.} {\bf 273} (2003), 103--114. \bibitem {CamLint} P.J. Cameron and J. van Lint, {\em Designs, Graphs, Codes and their Links}, London Mathematical Society Student Texts, 22, Cambridge, 1991. x+240 pp. \bibitem{C} C. Chen, Matchings and matching extensions in graphs, {\em Discrete Mathematics}. \textbf{186} (1998), 95--103. \bibitem {CGH} S.M. Cioab\u{a}, D.A. Gregory and W.H. Haemers, Matchings in regular graphs from eigenvalues, {\em J. Combin. Theory Ser. B} {\bf 99} (2009), 287--297. \bibitem{CKK} S.M. Cioab\u{a}, K. Kim and J.H. Koolen, On a conjecture of Brouwer involving the connectivity of strongly regular graphs, \emph{J. Combin. Theory Ser. A} \textbf{119} (2012), 904-922. \bibitem{CK} S.M. Cioab\u{a} and J.H. Koolen, On the connectedness of the complement of a ball in distance-regular graphs, \emph{J. Algebraic Combinatorics} {\bf 38} (2013), 191--195. \bibitem{CKL} S.M. Cioab\u{a}, J.H. Koolen and W. Li, Disconnecting strongly regular graphs, {\em European J. Combin.} {\bf 38} (2014), 1--11. \bibitem{DGS} Ph. Delsarte, J.-M. Goethals and J. J. Seidel, Spherical codes and designs, {\em Geom. Dedicata} {\bf 6} (1977), 363--388. \bibitem {EKKKN} L. Esperet, F. Kard\v{o}s, A.D. King, D. Kr\'{a}l and S. Norine, Exponentially many perfect matchings in cubic graphs, {\em Adv. Math.} {\bf 227} (2011), 1646--1664. \bibitem{FH} N.C. Fiala and W.H. Haemers, 5-chromatic strongly regular graphs, {\em Discrete Math.} {\bf 306} (2006), 3083--3096. \bibitem {F} S. Friedland, Results and open problems in matchings in regular graphs, {\em Electron. J. Linear Algebra} {\bf 24} (2012), 18--33. \bibitem{Gallai} T. Gallai, Neuer Beweis eines Tutte'schen Satzes, {\em Magyar Tud. Akad. Mat. Kut. Int. K\H{o}zl.} {\bf 8} (1963), 135--139. \bibitem {GR} C. Godsil and G. Royle, {\em Algebraic Graph Theory}, Springer Graduate Texts in Mathematics, 207. Springer-Verlag, New York, 2001. xx+439 pp. \bibitem {HL} D. Holton and D. Lou, Matching extensions of strongly regular graphs, {\em Australas. J. Combin.} {\bf 6} (1992), 187--208. \bibitem {Lovasz1} L. Lov\'{a}sz, On the structure of factorizable graphs. I, II., {\em Acta Math. Acad. Sci. Hung.} {\bf 23} (1972), 179--195; ibid. 23 (1972), 465--478. \bibitem{L} L. Lov\'{a}sz, {\em Combinatorial problems and exercises}. Second edition. North-Holland, Amsterdam, 1993. \bibitem{LP} L. Lov\'{a}sz and M.D. Plummer, {\em Matching Theory}, Corrected reprint of the 1986 original, AMS Chelsea, Providence, RI, 2009. xxxiv+554 pp. \bibitem {LZ} D. Lou and Q. Zhu, The 2-extendability of strongly regular graphs, \emph{Discrete Math}. \textbf{148} (1996), 133--140. \bibitem {Mohar} B. Mohar, Some applications of Laplace eigenvalues of graphs, Graph Symmetry: Algebraic Methods and Applications, Eds. G. Hahn and G. Sabidussi, NATO ASI Ser. C 487, Kluwer, (1997), 225--275. \bibitem {Plesnik} J. Plesn\'{i}k, Connectivity of regular graphs and the existence of $1$-factors, {\em Mat. \v{C}asopis Sloven. Akad. Vied} {\bf 22} (1972), 310--318. \bibitem{Plummer80} M.D. Plummer, On $n$-extendable graphs, {\em Discrete Math.} {\bf 31} (1980), 201--210. \bibitem{Plummer94} M.D. Plummer, Extending matchings in graphs: A survey, {\em Discrete Math.} {\bf 127} (1994), 277--292. \bibitem{Plummer08} M.D. Plummer, Recent progress in matching extension, {\em Building Bridges, Bolyai Soc. Math. Stud.}, {\bf 19}, Springer, Berlin, 2008, 427--454. \bibitem {Seidel} J.J. Seidel, Strongly regular graphs with $(-1, 1, 0)$ adjacent matrix having eigenvalue $3$, {\em Linear Alg. Appl.} {\bf 1} (1968), 281--298. \bibitem {Spielman} D. Spielman, Faster isomorphism testing of strongly regular graphs, {\em Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, STOC'96 (Philadelphia, PA, 1996)} (1996), 576--584. \bibitem {VanLintWilson} J.H. van Lint and R.M. Wilson, {\em A Course in Combinatorics}, Cambridge University Press 2nd Edition (2001). \bibitem{T} W.T. Tutte, The factorizations of linear graphs, \emph{J. London Math. Soc.} \textbf{22} (1947) 107-111. \bibitem {Yu} Q. Yu, Characterizations of various matching extensions in graphs, {\em Australas. J. Combin.} {\bf 7} (1993), 55--64. \bibitem {YuLiu} Q. Yu and G. Liu, {\em Graph Factors and Matching Extensions}, Higher Education Press, Beijing; Springer-Verlag, Berlin, 2009. xii+353 pp. %ISBN: 978-7-04-025758-8; 978-3-540-93951-1 \bibitem {ZZ} F. Zhang and H. Zhang, Construction for bicritical graphs and $k$-extendable bipartite graphs, {\em Discrete Math.} {\bf 306} (2006), 1415--1423. \end{thebibliography} \end{document}