Binding number and toughness for matching extension
type: Item
instance of: scholarly article
title: Binding number and toughness for matching extension
zbMATH Open document ID: 0837.05092
DOI: 10.1016/0012-365X(94)00175-5
author: Ciping Chen
published in: Discrete Mathematics
publication date: 1996-05-13T00:00:00Z
review text: 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.
reviewed by: Konrad Engel
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 825362
zbMATH Keywords: Tutte's theorem
zbMATH Keywords: binding number
zbMATH Keywords: toughness
zbMATH Keywords: neighbor set
zbMATH Keywords: number of components
zbMATH Keywords: matching
zbMATH Keywords: 1-factor
zbMATH Keywords: matching extension
MaRDI profile type: Publication
cites work: Tough graphs and Hamiltonian circuits.
cites work: Toughness and matching extension in graphs
cites work: The Factorization of Linear Graphs
cites work: The binding number of a graph and its Anderson number
description: scientific article; zbMATH DE number 825362