On Extendability of Cayley Graphs


Štefko Miklavič, Primož Šparl




A connected graph $\Gamma$ of even order is $n$-extendable, if it contains a matching of size $n$ and if every such matching is contained in a perfect matching of $\Gamma$. Furthermore, a connected graph $\Gamma$ of odd order is $n\frac12$-extendable, if for every vertex $v$ of $\Gamma$ the graph $\Gamma-v$ is $n$-extendable. It is proved that every connected Cayley graph of an abelian group of odd order which is not a cycle is 1$\frac12$-extendable. This result is then used to classify 2-extendable connected Cayley graphs of generalized dihedral groups.