The extendability of matchings in strongly regular graphs

Sebastian M Cioabă¹ ; Weiqiang Li¹

¹University of Delaware

The electronic journal of combinatorics, Tome 21 (2014) no. 2

Résumé

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.

Détail

DOI : 10.37236/4142

Classification : 05E30, 05C51, 05B15, 05B05, 05C70
Mots-clés : strongly regular graphs, matchings, extendability, triangular graphs, Latin square graphs, block graphs of Steiner systems