Binding number conditions for matching extension (Q1598823)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Binding number conditions for matching extension |
scientific article |
Statements
Binding number conditions for matching extension (English)
0 references
28 May 2002
0 references
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.
0 references
binding number
0 references
perfect matching
0 references
1-factor
0 references
extendable matching
0 references
matching extension
0 references