Tight lower bounds on the size of a maximum matching in a regular graph (Q2478167): Difference between revisions

A set of pairwise nonadjacent edges of a graph \(G\) is called a \textit{matching} in \(G\), while a matching of maximum cardinality is a \textit{maximum matching}. There are two recent very useful surveys on matchings in graphs: References [5] and [6] of the present paper. Recently some lower bounds are introduced for the size of a maximum matching in a regular graph (references [2] and [4]). In this paper also the authors by applying the well known Tutte-Berge formulation for the matching number \(\alpha'(G)\), i.e. \[ \alpha'(G)= \min_{X\subseteq V(G)} {\frac{1}{2}}(| V(G)| +| X| -\text{ oc}(G-X)), \] obtain interesting lower bounds for the size of a maximum matching in a regular graph. They show that for a connected \(k\)-regular graph \(G\), (i) if \(k\geq 2\) is even then, \[ \alpha'(G) \geq \min\{(\frac{k^2+4}{k^2+k+2})\times \frac{n}{2},\frac{n-1}{2}\}, \] (ii) if \(k\geq 3\) is odd then, \[ \alpha'(G) \geq \frac{(k^3-k^2-2)n-2k +2}{2(k^3-3k)}\cdot \] By constructing a class of regular graphs, in each case, they show that these bounds are realizable. We noticed the following misprints: On page 655 lines -11 and -10, all \(w\)'s should be \(v\)'s.