On the fractional matching extendability of Cayley graphs of Abelian groups

Abstract

Fractional matching extendability is a concept that brings together two widely studied topics in graph theory, namely that of fractional matchings and that of matching extendability. A {\em fractional matching} of a graph $\Gamma$ with edge set $E$ is a function $f$ from $E$ to the real interval $[0,1]$ with the property that for each vertex $v$ of $\Gamma$, the sum of $f$-values of all the edges incident to $v$ is at most $1$. When this sum equals $1$ for each vertex $v$, the fractional matching is {\em perfect}. A graph of order at least $2t+1$ is {\em fractional $t$-extendable} if it contains a matching of size $t$ and if each such matching $M$ can be extended to a fractional perfect matching in the sense that the corresponding function $f$ assigns value $1$ to each edge of $M$. In this paper, we study fractional matching extendability of Cayley graphs of Abelian groups. We show that, except for the odd cycles, all connected Cayley graphs of Abelian groups are fractional $1$-extendable and we classify the fractional $2$-extendable Cayley graphs of Abelian groups. This extends the classification of $2$-extendable (in the classical sense) connected Cayley graphs of Abelian groups of even order from 1995, obtained by Chan, Chen and Yu.

21 pages, this is a revised version submitted to the Electronic Journal of Combinatorics