Cycles containing many vertices of subsets in 1-tough graphs with large degree sums (Q2715952)

Let \(G\) be a graph of order \(n\) and let \(X\subset V(G)\). Denote by \(\alpha (X)\) the independence number of \(G[X]\) and by \(\sigma _k(X)\) the minimum degree sum over all independent subsets of size \(k\) of \(X\). Main result: Let \(G\) and \(X\subset V(G)\) be such that \(\sigma _3(X)\geq n\). (i) If \(G\) is 1-tough, then \(G\) contains a cycle \(C\) such that \(C\) is \(X\)-dominating (i.e. every vertex in \(X\setminus V(C)\) has all neighbors on \(C\)) and \(|V(C)\cap X|\geq \min \{|X|,|X|+1/3\sigma _3(X)-\alpha (X)\}\). (ii) If \(G\) is 2-tough, then \(G\) contains a cycle \(C\) with \(X\subset V(C)\).