The Induced Matching Extendability of $C_{2n}(1,k)$

Abstract

A simple graph $G$is induced matching extendable, shortly IM-extendable, if every induced matching of $G$ is included in a perfect matching of $G$. The cyclic graph $C_{2n}(1,k)$ is the graph with $2n$ vertices $x_0,x_1,\dots ,x_{2n-1}$, such that $x_i{x}_j$ is an edge of $C_{2n}(1,k)$ if either $i-j\equiv \pm 1(\mathrm{mod}2n)$ or $i-j\equiv \pm k(\mathrm{mod}2n)$. We show in this paper that the only IM-extendable graphs in $C_{2n}(1,k)$ are $C_{2n}(1,3)$ for $n\ge 4$; $C_{2n}(1,n-1)$ for $n\ge 3$; $C_{2n}(1,n)$ for $n\ge 2$; $C_{2n}(1,\frac{n}{2})$ for $n\ge 4$; $C_{2n}(1,\frac{2n+1}{3})$ for $n\ge 5$; $C_{2n}(1,\frac{2n+2}{3})$ for $n\le 14$; $C_{2n}(1,\frac{2n-2}{3})$ for $n\le 16$; $C_{2n}(1,2)$ for $n\le 4$; $C_{20}(1,8)$; $C_{30}(1,6)$; $C_{40}(1,8)$; $C_{60}(1,12)$ and $C_{80}(1,10)$.