A condition for a graph to contain \(k\)-matching. (Q1422440)

From MaRDI portal





scientific article; zbMATH DE number 2041920
Language Label Description Also known as
English
A condition for a graph to contain \(k\)-matching.
scientific article; zbMATH DE number 2041920

    Statements

    A condition for a graph to contain \(k\)-matching. (English)
    0 references
    14 February 2004
    0 references
    Let \(k,l\) and \(n\) be nonnegative integers such that \(1\leq k\leq n/2\). The author proves that if \(G\) is a graph of order \(n\), with minimum degree \(\delta(G)\geq l\) and size \(e(G)>\max \{f(n,k,l),f(n,k,k-1)\}\), where \(f(n,k,l)={2k-l-1\choose 2}+l(n-2k+l+1)\), then \(G\) contains a \(k\)-edge matching. The result is sharp when \(l\leq k-1\). More precisely, if \(e(G)=\max \{f(n,k,l),f(n,k,k-1)\}\) and \(G\) contains a \(k\)-edge matching then \(l\leq k-1\) and \(G=K_{2k-2p-1}*K_p*\overline{K}_{n-2k+p+1}\), where \(p\in \{ l,k-1\}\) and \(*\) is the operation of join of graphs.
    0 references
    0 references
    matching
    0 references
    forest
    0 references

    Identifiers