Toughness, degrees and 2-factors (Q1887644)

A \(2\)-factor of a graph is a \(2\)-regular spanning subgraph, i.e., the disjoint union of cycles that span the vertex set of the graph. The note under review discusses necessary conditions on a graph of order \(n\) such that it has \(2\)-factors with \(k\) cycles for \(1\leq k\leq C(n)\) and some constant \(C(n)\). The authors prove: If \(G\) is disconnected, \(n\geq 8\), and the minimum degree is at least \((n-4)/2\), then \(G\) contains a \(2\)-factor with \(k\) cycles for \(2\leq k\leq \lceil (n-4)/3\rceil\). If \(G\) is connected, \(n\geq 8\), \(G\) is not \(1\)-tough, and the minimum degree is at least \((n-4)/2\), then \(G\) contains a \(2\)-factor with \(k\) cycles for \(2\leq k\leq \lceil (n-4)/3\rceil\). Finally, if \(G\) is \(1\)-tough (i.e., \(G-S\) has at most \(| S| \) components for all nonempty subsets \(S\) of the vertex set), \(n\) is sufficiently large, and the minimum degree is at least \((n-t)/2\) for some \(0\leq t\leq 4\), then \(G\) contains a \(2\)-factor with \(k\) cycles where \(1\leq k\leq n/4-t\).