The toughness of cubic graphs (Q1911237)

If \(k(G)\) denotes the number of components of a graph \(G\), the toughness \(\tau(G)\) is defined as the minimum of \(|S|/k(G- S)\) taken over all sets \(S\) of vertices such that \(k(G- S)\geq 2\). New upper bounds for \(\tau(G)\) are presented for noncomplete cubic graphs on \(n\) vertices. In particular, it is shown that \(\tau(G)\leq \min\{(2n- 3\beta)/(n- \beta), 2\beta/(4\beta- n)\}\), where \(\beta\) is the independence number of \(G\). Another result is that \(\tau(G)\leq n/(n- a)\), where \(a\) is the minimum number of vertices whose removal from \(G\) leaves a bipartite graph. For a cycle permutation graph \(G\) satisfying a certain condition it is shown that \(\tau(G)\leq 4/3+ 4/(9m- 3)\), thus supporting a conjecture that the toughness of such graphs does not exceed 4/3.