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
matching
0 references
forest
0 references
0.8367618918418884
0 references
0.8321338891983032
0 references
0.8177280426025391
0 references
0.7941511869430542
0 references
0.7881211042404175
0 references