On Regular $(2,q)$-Extendable Graphs

Abstract

Let $G$ be a graph with a maximum matching of size $q$, and let $p\le q$ be a positive integer. Then $G$ is called $(p,q)$-extendable if every set of $p$ independent edges can be extended to a matching of size $q$. If $G$ is a graph of even order $n$ and $n=2q$, then $(p,q)$-extendable graphs are exactly the $p$-extendable graphs defined by Plummer $[11]$ in $1980$.

Let $d\ge 3$ be an integer, and let $G$ be a $d$-regular graph of order $n$ with a maximum matching of size $q=\frac{n-t}{2}\ge 3$ for an integer $t\ge 1$ such that $n–t$ is even. In this work, we prove that if

(i) $n\le (t+4)(d+1)-5$ or

(ii) $n\le (t+4)(d+2)–1$ when $d$ is odd,

then $G$ is $(2,q)$-extendable.