Binding number and toughness for matching extension
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.
- Matchings and matching extensions in graphs
- Binding number conditions for matching extension
- Toughness and matching extension in graphs
- Characterizing \(2k\)-critical graphs and \(n\)-extendable graphs
- Binding numbers and restricted fractional ( g , f )-factors in graphs
- Toughness, binding number and restricted matching extension in a graph
- Toughness and binding number
- Some results on binding number and fractional perfect matching
- Toughness and perfect matchings in graphs
- Binding number, toughness and general matching extendability in graphs
- Best monotone degree conditions for graph properties: a survey
- Matching extension and distance spectral radius
- Matching extension and matching exclusion via the size or the spectral radius of graphs
- Best monotone degree conditions for binding number
- Binding number, odd \([1, b]\)-factors and the distance spectral radius
- Spectral conditions for k-extendability and k-factors of bipartite graphs
- Spectral conditions for matching extension
- Matching extendability in Cartesian product of hypercubes and paths
- Extending unlocked matchings in graphs
- Extremal results for graphs with binding number strictly less than 1/r
This page was built for publication: Binding number and toughness for matching extension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1903741)
