
Sebastian M Cioabă

Weiqiang Li
Keywords:
Strongly regular graphs, matchings, extendability, triangular graphs, Latin square graphs, block graphs of Steiner systems
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 nonadjacent 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.
Author Biographies
Sebastian M Cioabă, University of Delaware
Department of Mathematical Sciences, Assistant Professor
Weiqiang Li, University of Delaware
Department of Mathematical Sciences, Ph.D. student