Binding number and toughness for matching extension (Q1903741): Difference between revisions

The binding number resp. the toughness of a simple graph \(G\) are defined by \[ \text{bind} (G) = \min \left\{ {\bigl |N_G(X) \bigr |\over |X |} : \varnothing \neq X \subset V(G) \text{ and } N_G(X) \neq V(G) \right\} \] resp. by \[ \text{tough} (G) = \min \left\{ {|X |\over w(G - X)} : X \subset V(G) \text{ and } w(G - X) \geq 2 \right\} \] where \(N_G(X)\) denotes the neighbor set of \(X\) in \(G\) and \(w(G - X)\) denotes the number of components of \(G - X\). Based on Tutte's 1-factor theorem, the author presents short proofs for the following result: Let \(G\) be a graph of even order and \(k \geq 1\). If \(\text{tough} (G) > k\) or \(\text{bind} (G) > \max \{k,(7k + 13)/12\}\) then every matching of size \(k\) in \(G\) can be extended to a 1-factor in \(G\). The case of \(\text{tough} (G) > k\) was settled earlier by \textit{M. D. Plummer} [Toughness and matching extension in graphs, Discrete Math. 72, No. 1-3, 311-320 (1988; 683.05034)] in a different way.