Cycles through prescribed vertices with large degree sum (Q1901041): Difference between revisions

Let \(G\) be a graph with vertex set \(V\) and let \(S\) be a set of vertices in \(G\). For vertices \(u\) and \(v\) of \(G\) define \(\kappa(u, v; G)\) to be the maximum number of disjoint paths from \(u\) to \(v\) in \(G\) and let \(\kappa(S; G)= \min\{\kappa(u, v; G)\mid u, v\in S\) and \(u\neq v\}\). Suppose \(S\) satisfies \(\kappa(S; G)\geq k\geq 2\). Denote by \(\sigma_{k+ 1}(S; G)\) the smallest degree sum of \(k+ 1\) independent vertices in \(S\). The author produces sharp lower bounds for \(\sigma_{k+ 1}(S; G)\) in terms of \(|V|\), \(k\) and the independence number of the induced subgraph \(G[S]\) to ensure that \(G\) has a cycle containing all vertices of \(S\). In particular, if \(G\) is \(k\)-connected, he gives bounds on \(\sigma_{k+ 1}(V; G)\) which guarantee that there is a Hamiltonian cycle.