Toughness of Induced Matching Extendable Graphs
Jing Li · 2010
Suppose every induced matching of G is included in a perfect matching of G,then G is induced matching extendable,shortly for IM-extendable.T(G) is used to denote the toughness of graph G.The main results are as follows:(1) Suppose that a graph G with 2n vertices is not complete(n ≥ 3),and G is IM-extendable,then 2/(n - 1) ≤ T(G) ≤ n - 1.(2) For any rational number p/q with 2/(n - 1) ≤ p/q ≤ n - 1,p + q ≤ 2n and 1 ≤ q ≤ n - 1,there is an IM-extendable graph with toughness p/q.