On transition matrices of Markov chains corresponding to Hamiltonian cycles

Konstantin Avrachenkov (), Ali Eshragh () and Jerzy A. Filar ()
Additional contact information
Konstantin Avrachenkov: INRIA
Ali Eshragh: The University of Newcastle
Jerzy A. Filar: Flinders University

Annals of Operations Research, 2016, vol. 243, issue 1, No 3, 19-35

Abstract: Abstract In this paper, we present some algebraic properties of a particular class of probability transition matrices, namely, Hamiltonian transition matrices. Each matrix $$P$$ P in this class corresponds to a Hamiltonian cycle in a given graph $$G$$ G on $$n$$ n nodes and to an irreducible, periodic, Markov chain. We show that a number of important matrices traditionally associated with Markov chains, namely, the stationary, fundamental, deviation and the hitting time matrix all have elegant expansions in the first $$n-1$$ n - 1 powers of $$P$$ P , whose coefficients can be explicitly derived. We also consider the resolvent-like matrices associated with any given Hamiltonian cycle and its reverse cycle and prove an identity about the product of these matrices. As an illustration of these analytical results, we exploit them to develop a new heuristic algorithm to determine a non-Hamiltonicity of a given graph.

Keywords: Markov Chain; Undirected Graph; Markov Decision Process; Hamiltonian Cycle; Probability Transition Matrix (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-014-1642-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:243:y:2016:i:1:d:10.1007_s10479-014-1642-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-014-1642-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().