Proof of the Hamiltonicity-trace conjecture for singularly perturbed Markov chains

We prove the conjecture formulated in Litvak and Ejov (2009), namely, that the trace of the fundamental matrix of a singularly perturbed Markov chain that corresponds to a stochastic policy feasible for a given graph is minimised at policies corresponding to Hamiltonian cycles. © 2011 Applied Probability Trust.SCOPUS: ar.j