Long cycles containing \(k\)-ordered vertices in graphs (Q2477380): Difference between revisions

A graph \(G\) on \(n\) vertices is said to be \(k\)-ordered hamiltonian for \(2\leq k\leq n\), if for every ordered set \(S\) of \(k\) distinct vertices, there is a cycle in \(G\) containing all of the vertices of \(S\) in the designated order. This concept was introduced by Chartrand but first used by Ng and Schulz. In this paper, the authors, establish the following result. Theorem. Let \(G\) be a \((k+2)\)-connected graph on \(n\) vertices and let \(S\) be an ordered set of \(k\) vertices. If there is is a cycle in \(G\) containing all of the vertices of \(S\) in the designated order, then there is such a cycle of length at least \(\min \{n,\sigma_2(G)\}\). This result qeneralizes several related results.