  We study a certain polytope depending on a graph $G$ and a parameter
$\beta\in(0,1)$ which arises from embedding the Hamiltonian cycle problem in a
discounted Markov decision process. Eshragh \emph{et al.} conjectured a lower
bound on the proportion of feasible bases corresponding to Hamiltonian cycles
in the set of all feasible bases. We make progress towards a proof of the
conjecture by proving results about the structure of feasible bases. In
particular, we prove three main results: (1) the set of feasible bases is
independent of the parameter $\beta$ when the parameter is close to 1, (2) the
polytope can be interpreted as a generalized network flow polytope and (3) we
deduce a combinatorial interpretation of the feasible bases. We also provide a
full characterization for a special class of feasible bases, and we apply this
to provide some computational support for the conjecture.
