Toughness and perfect matchings in graphs (Q2715945)
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: Toughness and perfect matchings in graphs |
scientific article; zbMATH DE number 1600918
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Toughness and perfect matchings in graphs |
scientific article; zbMATH DE number 1600918 |
Statements
30 May 2001
0 references
perfect matching
0 references
factor-critical graph
0 references
toughness
0 references
Toughness and perfect matchings in graphs (English)
0 references
Let \(G\) be a \(k\)-tough graph of order \(n\) with \(2k+2\leq n\). Then (i) the graph obtained from \(G\) by deleting any \(2k-1\) edges has a perfect matching, (ii) the graph obtained from \(G\) by deleting any \(2k\) vertices has a perfect matching. Both results are sharp. It should be noted that the second result was obtained independently by \textit{O. Favaron} [Discuss. Math., Graph Theory 16, No. 1, 41-51 (1996; Zbl 0865.05061)].
0 references
