\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2.34}{21(2)}{2014}

\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}}}


\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 29, 2014}{May 13, 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, $t<v/2$ and any matching of $t$ edges is contained in some perfect matching. The extendability of $G$ is the maximum $t$ such that $G$ is $t$-extendable. In this paper, we study the extendability properties of strongly regular graphs. We improve previous results and classify all strongly regular graphs that are not $3$-extendable. We also show that strongly regular graphs of valency $k\geq 3$ with $\lambda \geq 1$ are $\lfloor k/3\rfloor$-extendable (when $\mu \leq k/2$) and $\lceil \frac{k+1}{4}\rceil$-extendable (when $\mu>k/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, $t<v/2$ and any matching of size $t$ is contained in some perfect matching. Graphs that are $1$-extendable are also called matching covered (see Lov\'{a}sz and Plummer \cite[page 113]{LP}). A graph $G$ of odd order $v$ is called $t$-near-extendable (or $t\frac{1}{2}$-extendable in the notation of Yu \cite{Yu}) if it contains at least one near perfect matching, $t<(v-1)/2$ and for every vertex $x$, any matching of size $t$ that does not cover $x$, is contained in some near perfect matching that misses $x$. Graphs that are $0$-near-extendable are also called factor-critical or hypomatchable (see Lov\'{a}sz and Plummer \cite[page 89]{LP}). The extendability of a graph $G$ of even order is defined as the maximum $t< v/2$ such that $G$ is $t$-extendable; in this case, we say that the graph $G$ precisely $t$-extendable. The near-extendability of a graph $G$ of odd order is the largest $t<(v-1)/2$ such that $G$ is $t$-near-extendable; in this case, we say that $G$ is precisely $t$-near-extendable. In this paper, we will use the terms extendability and (precisely) $t$-extendable for graphs of even order and the terms near-extendability and (precisely) $t$-near-extendable for graphs of odd order.

Motivated among other things by work of Lov\'{a}sz \cite{Lovasz1} on canonical decomposition of graphs containing perfect matchings, the notion of extendability was introduced in 1980 by Plummer \cite {Plummer80} for graphs of even order, was later extended to graphs of odd order by Yu \cite{Yu} and has attracted a lot of attention (see the surveys \cite{Plummer94,Plummer08}, the book \cite{YuLiu} and the references therein). Zhang and Zhang \cite{ZZ} obtained an $O(mn)$ algorithm for determining the extendability of a bipartite graph $G$ of order $n$ and size $m$. At the present time, the complexity of determining the extendability of a non-bipartite graph is unknown. 

A graph $G$ is strongly regular with parameters $v, k, \lambda$ and $\mu$ (shorthanded $(v,k,\lambda,\mu)$-srg from now on) if it has $v$ vertices, is $k$-regular, any two adjacent vertices have exactly $\lambda$ common neighbors and any two non-adjacent vertices have exactly $\mu$ common neighbors. The study of strongly regular graphs lies at the intersection of graph theory, algebra and finite geometry \cite{BCN,BH2,BL,Cam,Cam2,GR,VanLintWilson} and has important applications in coding theory and computer science among others \cite{CamLint,Spielman}. A strongly regular graph is called imprimitive if it, or its complement, is disconnected. An imprimitive strongly regular graph is a disjoint union of cliques of the same order or a complete multipartite regular graph. The extendabilities of such graphs are easy to determine (see Subsection \ref{imprimitive}). 

In this paper, we study the extendability of primitive strongly regular graphs. Brouwer and Mesner \cite{BM} proved that the vertex-connectivity of any connected strongly regular graph equals its valency. Plesn\'{i}k  \cite{Plesnik} (or \cite[Chapter 7, Problem 30]{L}) showed that if $G$ is a $k$-regular and $(k-1)$-edge-connected graph with an even number of vertices, then the graph obtained by removing any $k-1$ edges of $G$, contains a perfect matching. It follows that every connected strongly regular graph is $1$-extendable. Holton and Lou \cite{HL} showed that strongly regular graphs with certain connectivity properties are $2$-extendable and conjectured that all but a few strongly regular graphs are $2$-extendable. Lou and Zhu \cite{LZ} proved this conjecture and showed that every connected strongly regular graph of valency $k\geq 3$ is $2$-extendable with the exception of the complete $3$-partite graph $K_{2,2,2}$ (the $(6,4,2,4)$-srg) and the Petersen graph (the $(10,3,0,1)$-srg). Another result worth mentioning is that any vertex-transitive graph is $1$-extendable or $0$-near-extendable (see \cite[Theorem 3.5.1]{GR} or \cite[Theorem 5.5.24]{LP}). For other results involving the extendability of vertex or edge-transitive graphs (with large cyclic connectivity) see Aldred, Holton and Lou \cite{AHL}. Many strongly regular graphs have trivial automorphism groups and our techniques are different than the ones used for vertex-transitive graphs.

In this paper, we show that every connected $(v,k,\lambda,\mu)$-srg of valency $k\geq 5$ is $3$-extendable with exception of the complete $4$-partite graph 
$K_{2,2,2,2}$ (the $(8,6,4,6)$-srg), the complement of the Petersen graph (the $(10,6,3,4)$-srg) and the Shrikhande graph (one of the two $(16,6,2,2)$-srgs). 
We also prove that any connected $(v,k,\lambda,\mu)$-srg with $\lambda \geq 1$ is $\lfloor k/3\rfloor $-extendable when $\mu \leq k/2$ and  $\lceil \frac{k+1}{4}\rceil$-extendable when $\mu >k/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$-near-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$-near-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$-near-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 $1<x_0<\frac{(k-\mu)(k-1)}{\mu}$. Also, $f'(x)>0$ 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 <k$, when $\theta_2 \geq 2$, we have $k/(-\theta_v)>2$, thus $\alpha(G)<v/3$. If $\theta_2=1$, then $\theta_v=\mu-k$ and $-\mu=\lambda-\mu=\theta_2+\theta_v=1+\mu-k$. Thus, $k=2\mu+1$ and $v=1+k+k(k-1)/\mu=3k+1=6\mu+4$. 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, $v=1-k+(k-\mu+1)g$. Hence, $g=\frac{8\mu+4}{\mu+2}=8-\frac{12}{\mu+2}$.  As $g$ is an integer, $\mu\in \{1,2,4,10\}$. When $\mu =4$ or $10$, we get $v>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| <v/2$. We can apply the same argument to $A^c$ and show that $e(A,A^c) \geq 5k-12$.
\end{proof}

\begin{lemma}\label{edgesinsideS}
Let $G$ be a primitive $(v,k,\lambda,\mu)$-srg and $S$ be a disconnecting set of vertices. If $G-S$ contains at least two singleton components, then $S$ contains at least $\mu(k-\mu)$ edges. 
\end{lemma}
\begin{proof}
Let $x$ and $y$ be two singleton components of $G-S$. Then $N(x)\cup N(y) \subseteq S$. If $z\in N(x) \setminus N(y)$, then $z$ and $y$ are non adjacent and they have exactly $\mu$ common. So, $z$ is adjacent to at least $\mu$ vertices of $S$, and there are $ |N(x) \setminus N(y)|=k-\mu$ such $z$. By the same argument, each vertex inside $N(y)\setminus N(x)$ is adjacent to at least $\mu$ vertices of $S$. Thus, $2e(S) \geq 2\mu(k-\mu)$. 
\end{proof} 

\section{The extendability of strongly regular graphs}

\subsection{Imprimitive strongly regular graphs}\label{imprimitive}

A strongly regular graph is imprimitive if it, or its complement, is disconnected. The only imprimitive strongly regular graphs are disjoint unions of cliques of the same order and their complements (complete multipartite regular graphs). A disjoint union $mK_a$ of some number $m\geq 2$ of cliques $K_a$ does not contain a perfect matching nor a near perfect matching if $a$ is odd. If $a$ is even, the extendability of this graph is $am/2-1$. The complete multipartite graph $K_{a\times m}$ (which is the complement of $mK_a$) has extendability $am/2-1$ if $m=2$. When $m\geq 3$, if $am$ is even, the extendability of $K_{a\times m}$ is $\frac{a(m-2)}{2}=\frac{k-a}{2}$ and if $am$ is odd, the near-extendability of $K_{a\times m}$ is $\frac{a(m-2)-1}{2}=\lfloor\frac{k-a}{2}\rfloor$.

%Let $G$ be a $K_{a\times m}$ and $x$ be a vertex of $G$. Then the graph induced by $N(x)$ is $K_{a\times(m-1)}$, which is also a strongly regular graph. Let $S=N(x)$. Now, $S$ contains a matching of size $a(m-2)/2+1$ and $o(G-S)=a$. So, $a=o(G-S)\geq |S|-2(a(m-2)/2+1)+2=a$. By Lemma \ref{notn}, $G$ is not ($a(m-2)/2+1$)-extendable.  If $G$ is not ($a(m-2)/2$)-extendable, by Lemma \ref{notn}, there is a disconnecting set $S$ in $G$, such that $S$ contains $a(m-2)/2$ independent edges and $o(G-S)\geq |S|-a(m-2)+2$. As the independence number is $a$ and  $|S|\geq k=a(m-1)$, we have $a\geq a+2$, which is a contradiction. 


\subsection{$\!\!$Lower bounds for the extendability of strongly regular graphs$\!$}

In this section, we classify the primitive strongly regular graphs of even order that are not $3$-extendable. We first provide results giving some general lower bounds for the extendability of a primitive strongly regular graphs.
\begin{theorem}\label{srgn2}
 If $G$ is a $(v,k,\lambda,\mu)$-srg with $v$ even and $k/2<\mu<k$ and $\alpha(G) \geq 3$, then the extendability of $G$ is at least $\max \left(\lceil \frac{k+3}{2}-\frac{3k-2\lambda-3}{2(2\theta_2+1)}\rceil -1,\lceil \lambda/2+1 \rceil \right)$. 
\end{theorem}
\begin{proof}
Since $\mu>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-\mu<k/2$. By  the Hoffman-ratio bound \cite{BH,GR}, $\alpha(G)\leq \frac{v}{1+k/(-\theta_v)}<\frac{v}{1+2\theta_2}$.  Combining these inequalities, we get that $\alpha(G)\leq \frac{3k-2\lambda-3}{1+2\theta_2}$. The second subconstituent $\Gamma_2(x)$ is connected (see \cite[Proposition 9.3.1]{BH2}) and $|N_2(x)|=k(k-\lambda-1)/\mu<2(k-\lambda-1)$. Thus, $\alpha(G)\leq 1+\frac{|N_2(x)|}{2}$ which implies $\alpha(G)\leq k-\lambda-1$. By Lemma \ref{esrgindependence}, the extendability of $G$  is at least 
$\max \left(\lceil \frac{k+3}{2}-\frac{3k-2\lambda-3}{2(2\theta_2+1)}\rceil -1,\lceil \lambda/2+1 \rceil \right)$.
\end{proof}

Note that the bounds in Theorem \ref{srgn2} are incomparable. When $\theta_2=1$, the first bound gives us $\lceil \lambda/3+1\rceil$ and the second bound $\lceil \lambda/2+1 \rceil$ is better. On the other hand, when $\lambda=k/2$ and $\theta_2 \geq 2$, the first bound gives us $\lceil 3k/10+4/5 \rceil$ which is better than the second bound $\lceil k/4+1\rceil$. There exist strongly regular graphs with $\lambda=k/2$ and $\theta_2\geq 2$, for example, the $(36,20,10,12)$-srg.  

\begin{corollary}\label{k8mularge}
Any primitive $(v,k,\lambda,\mu)$-srg with $v$ even, $\mu>k/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<k$, then $\lambda\geq k/2+1>\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<\mu<k$, then $G$ is $m$-extendable, where $m=\lceil \frac{(k-3)(k-2)[(k(k-1)-(k-3)\mu]+(k-3)\mu+k}{(3k-7)[(k-3)\mu+k]}\rceil-1$.
\end{theorem}
\begin{proof}
%Assume $\mu\leq k/2$. 
If $G$ is not $n$-extendable, by Lemma \ref{notn}, there is a vertex set $S$ with $s$ vertices such that $S$ contains $n$ independent edges, and $G-S$ has at least $s-2n+2$ odd components. Let $O_1, O_2, \dots, O_r$ be all the odd components of $G-S$, with $r\geq s-2n+2$. Let $a\geq 0$ denote the number singleton components among $O_1,\dots,O_r$.
Counting the number of edges between $S$ and $O_1\cup \dots \cup O_r$ and using Lemma \ref{srgoutedge}, we get the following
\begin{equation}
ks-2n\geq e(S,O_1\cup \dots \cup O_r)\geq ak+(r-a)(3k-6)\geq ak+(s-2n+2-a)(3k-6).
\end{equation}
This inequality is equivalent to 
\begin{equation}\label{ineqsa}
n\geq \frac{(k-3)(s-a)+3k-6}{3k-7}
\end{equation}
and since $s-a\geq k-1$ (see the remark following Lemma \ref{Independentset3}), we obtain that
\begin{equation}
n\geq \frac{(k-3)(k-1)+3k-6}{3k-7}=\frac{k^2-k-3}{3k-7}.
\end{equation}
This is a contradiction with $n=\lceil \frac{k^2-k-3}{3k-7}\rceil-1<\frac{k^2-k-3}{3k-7}$. 
%The proof for the case $\mu>k/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<\mu<k$, $\lambda \leq 2$ and $\theta_2=1$. If $\theta_2=1$, then $-\theta_v=k-\mu, 1+\theta_v=\lambda-\mu$ and consequently, $k+\lambda-1=2\mu>k$ 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)<v\leq 2\alpha(G)+4$ and  $k\leq \alpha(G)<4$, which contradicts to $k\geq 8$. If $G-S$ has at most one singleton component, as $o(G-S)\geq |S|-4\geq 3$, $G-S$ has at least two non-singleton components, thus $|S|\geq k+1$. By using Lemma \ref{tfsrgedgecut} and counting the edges between $S$ and $O_1\cup \dots \cup O_r$, we will get the following,
$$k|S|-6\geq e(S,O_1\cup \dots \cup O_r)\geq k+(|S|-5)(5k-12)
$$
which implies that
$$12k-33\geq (2k-6)|S| \geq (2k-6)(k+1).
$$
Thus, $2k^2-16k+27\leq 0$, contradiction with $k\geq 8$.

If $G-S$ has at least one non-singleton components and at least two singleton components, by using Lemma \ref{tfsrgedgecut} and Lemma \ref{edgesinsideS} and  counting the edges between $S$ and $O_1\cup \dots \cup O_r$, we will get that
$$k|S|-2(k-1)\geq k|S|-2\mu(k-\mu)\geq k|S|-2e(S)\geq e(S,O_1\cup \dots \cup O_r)\geq 5k-12+(|S|-5)k
$$
which will yield another contradiction with $k\geq 8$.
\end{proof}

Note that this theorem covers all known primitive triangle-free strongly regular graph with even order with precisely three exceptions. These are the Petersen graph, which is the unique $(10,3,0,1)$-srg (and has extendability $1$ as shown in \cite{LZ}), the folded 5-cube, which is the unique $(16,5,0,2)$-srg (and has extendability $3$; see Theorem \ref{fold}) and the Hoffman-Singleton graph, which is the unique $(50,7,0,1)$-srg (and has extendability $5$; see Theorem \ref{HS}).

\begin{corollary}
Let $G$ be a primitive $(v,k,\lambda,\mu)$-srg with $v$ even and $k\geq 5$. Then $G$ is $3$-extendable unless $G$ is the complete $4$-partite graph 
$K_{2,2,2,2}$ (the $(8,6,4,6)$-srg), the complement of the Petersen graph (the $(10,6,3,4)$-srg) or the Shrikhande graph (one of the two $(16,6,2,2)$-srgs). 
\end{corollary}
\begin{proof}
If $k\geq 8$, then $G$ is $3$-extendable by Corollary \ref{3lambda1} and Theorem \ref{3trianglefree}. There are two primitive parameter sets with $v$ even, $\lambda \geq 1$ and $5\leq k\leq 7$: $(10,6,3,4)$ and $(16,6,2,2)$. There is a unique $(10,6,3,4)$-srg, the complement of Petersen graph or the triangular graph $T(5)$. Theorem \ref{eventriangular} will show that the extendability of this graph is $2$. There are two non-isomorphic strongly regular graphs with parameter set $(16,6,2,2)$. One is the Shrikhande graph (see \cite[page 123]{BH2} for a description) and the other is the line graph of $K_{4,4}$. In the Shrikhande graph, the first subconstituent of a fixed vertex is isomorphic to the cycle $C_6$ and thus, contains a matching of size $3$. This matching is not contained in any perfect matching. Thus, the Shrikhande graph is not $3$-extendable; by Lou and Zhu \cite{LZ}, the extendability of the Shrikhande graph is $2$. Proposition \ref{line} will show that the extendability of the line graph of $K_{4,4}$ is $3$. To finish the proof, the only strongly regular graph with $5\leq k\leq 7$ and $\lambda=0$ is the folded $5$-cube whose extendability is $3$ (see Theorem \ref{fold}).
\end{proof}

By a more extensive case analysis which we omit here, we can show that a primitive strongly regular graph of even order and valency $k\geq 9$ is $4$-extendable. Similarly, we can show that every strongly regular graph of odd order and valency $k\geq 3$ is $1$-near-extendable. Also, there is exactly one primitive strongly regular graph with $k \geq 3$ which is not $2$-near-extendable, namely the Paley graph on $9$ vertices (the unique $(9,4,1,2)$-srg).


\section{The extendability of some specific strongly regular graphs}\label{section3}

In this section, we determine the extendability of several families of strongly regular graphs. In the first three subsections, we show that there are many strongly regular graphs with extendability equal or slightly larger than  $\lceil k/2\rceil -1$. In the last subsection, we show that the extendability of any known triangle-free strongly regular graph of even order and valency $k$ equals $k-2$.

The reason that the graphs considered in the next three subsections (except for the graphs in Theorem \ref{line}) are not $\lceil k/2 \rceil$-extendable (when $v$ is even) or not $k/2$-near-extendable (when $v$ is odd) is the following.  Consider the first subconstituent $\Gamma_1(x)$ of any fixed vertex $x$; this is the subgraph induced by $N(x)$. If $v$ is even, we will show that $\Gamma_1(x)$ has a matching of size $k/2$ if $k$ is even and of size $(k-1)/2$ if $k$ is odd. When $k$ is odd, there is one vertex $y$ not covered by the matching of size $(k-1)/2$ and we choose a vertex $z$ not adjacent to $x$ such that $z$ is adjacent with $y$. In each case, we construct a matching of size $\lceil \frac{k}{2}\rceil$ that cannot be contained in a perfect matching since its removal leaves $x$ isolated. If $v$ is odd, then $k$ is even. We will show that $\Gamma_1(x)$ has a matching of size $k/2$. Choose a vertex $y\in N_2(x)$. The matching of size $k/2$ in $\Gamma_1(x)$ does not cover $y$. Thus, we construct a matching that cannot be contained in a near perfect matching that misses $y$ since the removal of $N(x)\cup \{y\}$ leaves $x$ isolated. We will also use the following lemma. 
\begin{lemma}\label{N(x)}
Let $G$ be a graph of order $am$ whose vertex set can be partitioned into $m$ subsets, $A_1, A_2, \ldots, A_m$ with equal size $a$, such that for $1\leq i \leq m$, $A_i$ induce a clique, and the graph obtained by vertex contracting each $A_i$ contains a perfect matching (when $m$ is even)  or a near perfect matching (when $m$ is odd). Then $G$ contains a perfect matching if $am$ is even, and $G$ contains a near perfect matching if $am$ is odd.   
\end{lemma}
\begin{proof}
If $a$ is even, the lemma is obvious. If $a$ is odd and $m$ is even, we can find a matching $u_1u_2, \cdots, u_{m-1}u_m$ such that $u_i\in A_i$ for $1\leq i \leq m$. Now, each subgraph induced by $A_i\setminus u_i$ contain a perfect matching. Thus $G$ contains a perfect matching. If $a$ is odd and $m$ is odd, we can find a matching $u_1u_2, \cdots, u_{m-2}u_{m-1}$ such that $u_i\in A_i$ for $1\leq i \leq m-1$. Now, each subgraph induced by $A_i\setminus u_i$ contain a perfect matching for $1\leq i \leq m-1$ and $A_m$ contains a near perfect matching. Thus $G$ contains a near perfect matching. 
\end{proof}

\subsection{Triangular graphs}

The triangular graph $T(m)$ is the line graph of the complete graph $K_m$; its vertices are the 2-subsets of $[m]:=\{1,\ldots,m\}$ and $\{u,v\}\sim\{x,y\}$ if and only if $|\{u,v\}\cap \{x,y\}|=1$. The triangular graph $T(m)$ is an $({m \choose 2}, 2(m-2),m-2,4)$-srg. 
\begin{theorem}\label{eventriangular}
Let $m$ be an integer such that $m\geq 4$ and ${m\choose 2}$ is even. The extendability of $T(m)$ is $k/2-1=m-3$.
\end{theorem}
\begin{proof} 
The subgraph induced by $N(\{1,2\})$ contains a perfect matching. \\
Take $\{(\{1,i\},\{2,i\})| 3\leq i \leq m\}$ for example. By the observation at the beginning of Section \ref{section3}, this shows that $T(m)$ is not $(m-2)$-extendable. 

Assume that $T(m)$ is not $(m-3)$-extendable. By Lemma \ref{notn}, there is a subset of vertices $S$ such that $S$ contains $m-3$ independent edges and $r=o(G-S)\geq |S|-2(m-3)+2$. Let $O_1, O_2, \ldots, O_r$ be the odd components of $G-S$. Denote by $P_i$ the union of the $2$-subsets corresponding to the vertices of $O_i$, for $1\leq i \leq r$. If $r\leq 3$, then by Theorem \ref{kconnected}, $|S|\geq 2(m-2)$ and therefore, $3\geq o(G-S)\geq |S|-2(m-3)+2\geq 4$, contradiction. If $r\geq 4$, then since $P_1, P_2, \ldots, P_r$ are disjoint subsets of $[m]$, and $|P_i|\geq 2$, we have $m\geq 8$. There exists two odd components, say $O_1, O_2$, such that $3\leq |P_1\cup P_2| \leq m-3$. We have $\{ \{u,v\} \mid u\in P_1\cup P_2, v\in [m]-(P_1\cup P_2)\}\subset N(O_1\cup O_2)\subset S$. Thus $|S| \geq 3(m-3)$. On the other hand, as $2r\leq |P_1|+ |P_2|+ \ldots+ |P_r|\leq m$, we have $r\leq m/2$.  So, $m/2\geq o(G-S)\geq |S|-2(m-3)+2\geq 3(m-3)-2(m-3)+2=m-1$, contradiction with $m\geq 8$.
\end{proof}

\begin{theorem}\label{oddtriangular}
Let $m$ be an integer such that $m\geq 6$ and ${m\choose 2}$ is odd. The near-extendability of $T(m)$ is $k/2-1=m-3$.
\end{theorem}
\begin{proof}
By a similar argument as above, it is easy to see that $T(m)$ is not $(m-2)$-near-extendable. Assume that $T(m)$ is not $(m-3)$-near-extendable. By Lemma \ref{notn1/2}, there is a subset of vertices $S$ such that $S$ contains $m-3$ independent edges, $|S|\geq 2(m-3)+1$ and $r=o(G-S)\geq |S|-2(m-3)+1$. If $r=2$, then by Theorem \ref{kconnected}, $|S|\geq 2(m-2)$ and therefore, $2= o(G-S)\geq |S|-2(m-3)+1\geq 3$, contradiction. If $r=3$, $S$ is not the neighborhood of some vertex.  By Theorem \ref{kconnected}, $|S|\geq 2(m-2)+1$, and therefore, $3= o(G-S)\geq |S|-2(m-3)+1\geq 4$, contradiction. The rest of the proof is similar to the proof of Theorem \ref{eventriangular}.
\end{proof}



\subsection{Block graphs of Steiner systems}

A 2-$(n,K,1)$-design or a Steiner $K$-system is a point-block incidence structure on $n$ points such that each block has $K$ points and any two distinct points are contained in exactly one block. The block graph of such a Steiner system has as vertices the blocks and two distinct blocks are adjacent if they intersect. The block graph of a Steiner $K$-system is a $\left(\frac{n(n-1)}{K(K-1)}, \frac{K(n-K)}{K-1}, (K-1)^2+\frac{n-1}{K-1}-2, K^2\right)$-srg. 

\begin{theorem}\label{design}
Let $G$ be the block graph of a Steiner $K$-system on $n$ points such that $\frac{n(n-1)}{K(K-1)}$ is even. If $K\in \{3,4\}$ and $n>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 near-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 near-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 near-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)$-near-extendable. The proof that $G$ is $(n-2)$-near-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 near-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 near-extendability of the known triangle-free strongly regular graphs with odd order. The $(5,2,0,1)$-srg is precisely $0$-near-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$-near-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$-near-extendable.  

If $G$ were not $13$-near-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 near-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 
\url{http://www.win.tue.nl/~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}
