Toughness of graphs and the existence of factors (Q1813740): Difference between revisions

The toughness \(t(G)\) of a graph \(G\) is the largest real number \(t\) such that the deletion of any \(s\) vertices from \(G\) results in a graph which is either connected or else has at most \(s/t\) components. This concept was introduced by Chvátal, who conjectured that if \(G\) is a graph, \(k\) is a positive integer such that \(k| V(G)|\) is even and \(t(G)\geq k\), then \(G\) has a \(k\)-factor. This conjecture was subsequently proved by \textit{H. Enomoto, B. Jackson, A. Saito} and the author [``Toughness and the existence of \(k\)-factors'', J. Graph Theory 9, 87-95 (1985; Zbl 0598.05054)]. The paper under review derives two new theorems, both of which contain Chvátal's conjecture as a special case. The more easily stated of these is the following. Let \(G\) be a graph and let \(a\) and \(b\) be positive integers with \(a\leq b\). If \(a=b\) assume that \(a| V(G)|\) is even. Then \(G\) has an \([a,b]\)-factor if \(t(G)\geq a-1+{a\over b}\). An \([a,b]\)-factor is a spanning subgraph such that each vertex has degree \(a\) or \(b\).