Long Paths Containing $k$-Ordered Vertices in Graphs

Abstract

Let $G$ be a graph on $n$ vertices. If for any ordered set of vertices $S=\{v_1,v_2,\dots ,v_k\}$, where the vertices in $S$ appear in the sequence order $v_1,v_2,\dots ,v_k$, there exists a $v_1-v_k$ (Hamiltonian) path containing $S$ in the given order, then $G$ is $k$-ordered (Hamiltonian) connected. In this paper, we show that if $G$ is $(k+1)$-connected and $k$-ordered connected, then for any ordered set $S$, there exists a $v_1-v_k$ path $P$ containing $S$ in the given order such that $|P|\ge min\{n,{\sigma }_2(G)–1\}$, where ${\sigma }_2(G)=min\{d_G(u)+d_G(v):u,v\in V(G);uv\notin E(G)\}$ when $G$ is not complete, and ${\sigma }_2(G)=\mathrm{\infty }$ otherwise. Our result generalizes several related results known before.