On the Order of Close to Regular Graphs Without a Matching of Given Size

Abstract

A graph \(G\) is a \((d,d+k)\)-graph, if the degree of each vertex of \(G\) is between \(d\) and \(d+k\). Let \(p > 0\) and \(d+k \geq 2\) be integers. If \(G\) is a \((d,d+k)\)-graph of order \(n\) with at most \(p\) odd components and without a matching \(M\) of size \(2|M| = n – p\), then we show in this paper that

1. \(n \geq 2d+p+2\) when \(p \leq k-2\),
2. \(n \geq 2\left\lceil \frac{d(p+2)}{k} \right\rceil +p +2\) when \(p \geq k-1\).

Corresponding results for \(0 \leq p \leq 1\) and \(0 \leq k \leq 1\) were given by Wallis \([6]\), Zhao \([8]\), and Volkmann \([5]\).

Examples will show that the given bounds (i) and (ii) are best possible.