  A bipartite graph is chordal bipartite if every cycle of length at least six
has a chord in it. M$\ddot{\rm u}$ller \cite {muller1996Hamiltonian} has shown
that the Hamiltonian cycle problem is NP-complete on chordal bipartite graphs
by presenting a polynomial-time reduction from the satisfiability problem. The
microscopic view of the reduction instances reveals that the instances are
$P_9$-free chordal bipartite graphs, and hence the status of Hamiltonicity in
$P_8$-free chordal bipartite graphs is open. In this paper, we identify the
first non-trivial subclass of $P_8$-free chordal bipartite graphs which is
$P_5$-free chordal bipartite graphs, and present structural and algorithmic
results on $P_5$-free chordal bipartite graphs. We investigate the structure of
$P_5$-free chordal bipartite graphs and show that these graphs have a {\em
Nested Neighborhood Ordering (NNO)}, a special ordering among its vertices.
Further, using this ordering, we present polynomial-time algorithms for
classical problems such as the Hamiltonian cycle (path), also the variants and
generalizations of the Hamiltonian cycle (path) problem. We also obtain
polynomial-time algorithms for treewidth (pathwidth), and minimum fill-in in
$P_5$-free chordal bipartite graph. We also present some results on complement
graphs of $P_5$-free chordal bipartite graphs.
