Toughness and matching extension in graphs (Q1824634): Difference between revisions

The author gives two results connecting the toughness of a graph with its matching extendability. Let G be a graph with a perfect matching, G is said to be n-extendable if every matching of size n in G extends to a perfect matching. The toughness of G, denoted tough(G), is the minimum over all vertex cutsets S of the quantity \(| S| /c(G-s)\) where c(G-S) is the number of components of G-S. The author proves the following results: 1. If \(tough(G)>n\), a positive integer, then G is n- extendable. 2. If G has p vertices, G is n-extendable, and \(tough(G)<1\) then \(n\leq (p-2)/6\).