Binding number conditions for matching extension
type: Item
instance of: scholarly article
title: Binding number conditions for matching extension
zbMATH Open document ID: 0990.05102
DOI: 10.1016/S0012-365X(01)00192-3
author: Andrew M. Robertshaw
author: Douglas R. Woodall
published in: Discrete Mathematics
publication date: 2002-05-28T00:00:00Z
review text: A graph is \(k\)-extendable if it has a \(k\)-matching and every such matching is extendable to a perfect matching (1-factor). The binding number of a graph is the minimum value of \(|N(X)|/|X|\) over non-empty sets of vertices \(X\) for which neighbourhood \(N(X)\) is not the whole graph. This paper gives a lower bound on the binding number, in terms of \(k\) and the number of vertices, which is sufficient to guarantee that a graph is \(k\)-extendable. A family of examples is constructed to show that the bound is best possible for some values of the parameters.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1746258
zbMATH Keywords: binding number
zbMATH Keywords: perfect matching
zbMATH Keywords: 1-factor
zbMATH Keywords: extendable matching
zbMATH Keywords: matching extension
reviewed by: Ian M. Wanless
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00192-3
OpenAlex ID: W2054195094
Recommended article: Binding number and toughness for matching extension
Recommended article: Q4871750
Recommended article: Q2940118
Recommended article: Condition numbers and their condition numbers
Recommended article: Q3976970
Recommended article: Binding numbers and connected factors
Recommended article: Counting extensions
Recommended article: Matching extension and minimum degree
Recommended article: Q3605289
description: scientific article; zbMATH DE number 1746258