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, \ldots, x_{2n-1}\), such that \(x_ix_j\) is an edge of \(C_{2n}(1,k)\) if either \(i-j \equiv \pm 1 \pmod{2n}\) or \(i-j \equiv \pm k \pmod{2n}\). We show in this paper that the only IM-extendable graphs in \(C_{2n}(1,k)\) are \(C_{2n}(1,3)\) for \(n \geq 4\); \(C_{2n}(1,n-1)\) for \(n \geq 3\); \(C_{2n}(1,n)\) for \(n \geq 2\); \(C_{2n}(1,\frac{n}{2})\) for \(n \geq 4\); \(C_{2n}(1,\frac{2n+1}{3})\) for \(n \geq 5\); \(C_{2n}(1,\frac{2n+2}{3})\) for \(n \leq 14\); \(C_{2n}(1,\frac{2n-2}{3})\) for \(n \leq 16\); \(C_{2n}(1,2)\) for \(n \leq 4\); \(C_{20}(1,8)\); \(C_{30}(1,6)\); \(C_{40}(1,8)\); \(C_{60}(1,12)\) and \(C_{80}(1,10)\).