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

V. Ejov, Nelli Litvak, G. Nguyen

Research output: Book/ReportReportProfessional

201 Downloads (Pure)


We prove the conjecture formulated in the paper by N. Litvak and V. Ejov ("Markov Chains and Optimality of The Hamiltonian Cycle", to appear in Math. Oper. Res., 2008), namely, that the trace of the fundamental matrix of a singularly perturbed Markov chain is minimized at policies corresponding to Hamiltonian cycles, over the set of all stochastic policies feasible for a given graph.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages10
Publication statusPublished - Jun 2008

Publication series

PublisherDepartment of Applied Mathematics, University of Twente
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850


  • IR-64811
  • METIS-251008
  • MSC-11C20
  • MSC-05C45
  • MSC-60J10
  • EWI-12877

Cite this