The extendability of matchings in strongly regular graphs (Q405235)

Summary: 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.