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 this page instead for the normal view: A condition for a graph to contain \(k\)-matching. |
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
matching
0 references
forest
0 references