Toughness and Perfect Matchings in Graphs

Guizhen Liu1, Qinglin Yu2,3
1 Department of Mathematics Shandong University Jinan, Shandong P.R. China
2 Department of Mathematics University College of The Caribou Kamloops, BC, Canada
3Department of Mathematics and Statistics Simon Fraser University Burnaby, BC, Canada

Abstract

Let \(G\) be a graph with even order \(p\) and let \(k\) be a positive integer with \(p \geq 2k + 2\). It is proved that if the toughness of \(G\) is at least \(k\), then the subgraph of \(G\) obtained by deleting any \(2k – 1\) edges or \(k\) vertices has a perfect matching. Furthermore, we show that the results in this paper are best possible.