On The Number of Edge-Disjoint Almost Perfect Matchings in Regular Odd Order Graphs

Abstract

Let $G$ be a $k$-regular graph of odd order $n\ge 3$ with $k\ge \frac{n+1}{2}$. This implies that $k$ is even. Furthermore, let
$$p=min\{\frac{k}{2},\lceil k-\frac{n}{3}\rceil \}.$$
If $x_1,x_2,\dots ,x_p$ are arbitrary given, pairwise different, vertices of the graph $G$, then we show in this paper that there exist $p$ pairwise edge-disjoint almost perfect matchings $M_1,M_2,\dots ,M_p$ in $G$ with the property that no edge of $M_i$ is incident with $x_i$ for $i=1,2,\dots ,p$.