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
    0 references
    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

    Identifiers