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

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 2041920
Language Label Description Also known as
default for all languages
No label defined
    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
      0 references

      Identifiers