On \(k\)-ordered bipartite graphs (Q1871375)

Summary: In 1997, \textit{L. Ng} and \textit{M. Schultz} [J. Graph Theory 24, 45-57 (1997; Zbl 0864.05062)] introduced the idea of cycle orderability. For a positive integer \(k\), a graph \(G\) is \(k\)-ordered if for every ordered sequence of \(k\) vertices, there is a cycle that encounters the vertices of the sequence in the given order. If the cycle is also a Hamiltonian cycle, then \(G\) is said to be \(k\)-ordered Hamiltonian. We give minimum degree conditions and sum of degree conditions for nonadjacent vertices that imply a balanced bipartite graph to be \(k\)-ordered Hamiltonian. For example, let \(G\) be a balanced bipartite graph on \(2n\) vertices, \(n\) sufficiently large. We show that for any positive integer \(k\), if the minimum degree of \(G\) is at least \((2n+k-1)/4\), then \(G\) is \(k\)-ordered Hamiltonian.