Long paths with endpoints in given vertex-subsets of graphs (Q941396)

It is proved that if \(G\) is a connected graph of order \(n\) and \(t \geq 1\) a real number, and \(M\) is a set of vertices with \(| M| \geq n/t \geq 2\), then for any vertex \(v \in G\), there is a vertex \(u \in M\) with a path \(P\) from \(v\) to \(u\) such that \[ | P| \geq \min\left\{\frac{4}{4+t}d_G(u) + \frac{4-2t}{4+t}, \frac{2}{1+t}d_G(u) - 1, d_G(u) + 1 - t\right\}. \] It is also shown under the same conditions on \(G\), \(M\), \(n\) and \(t\) that either there is a cycle \(C\) containing all vertices of \(M\) or there exists a path \(P\) in \(G\) from vertices \(u_o\) to \(u_p\) in \(M\) such that \[ | P| \geq \min\left\{n, \frac{f(t)}{1+t(t)}(d_G(u_0) + d_G(u_p)) - 2t - \frac{6}{1+f(t)}\right\}. \] where \(f(t) = \min \{\frac{4}{t}, \frac{2}{t-1}\}\). These results are related to and motivated by the concept of cyclable sets of vertices.