Cycles through subsets with large degree sums (Q1363686): Difference between revisions

Let \(G\) be a 2-connected graph on \(n\) vertices and let \(X\subseteq V(G)\). The paper deals with various conditions that ensure that \(G\) has a cycle covering all vertices of \(X\) (in which case \(G\) is \(X\)-cyclable). The conditions are expressed in terms of various parameters related to \(X\). Let \(\alpha(X)\) denote the independence number of the subgraph \(G[X]\) induced by \(X\). If \(G[X]\) is not complete, then \(\kappa(X)\) denotes the minimum cardinality of a set of vertices of \(G\) separating two vertices in \(X\). Denote by \(\delta(X)\) the minimum degree in \(G\) among the vertices in \(X\). Finally, \(\sigma_3(X)\) denotes the minimum value of the degree sum (in \(G\)) of any three pairwise nonadjacent vertices of \(X\). The main results of the paper are: (i) If \(\sigma_3(X)\geq n+\min\{\kappa(X), \delta(X)\}\), then \(G\) is \(X\)-cyclable. (ii) If \(\alpha(X)\leq\kappa(X)\), then \(G\) is \(X\)-cyclable.