TY - JOUR

T1 - On transition matrices of Markov chains corresponding to Hamiltonian cycles

AU - Avrachenkov, Konstantin

AU - Eshragh, Ali

AU - Filar, Jerzy

PY - 2016/8/1

Y1 - 2016/8/1

N2 - In this paper, we present some algebraic properties of a particular class of probability transition matrices, namely, Hamiltonian transition matrices. Each matrix P in this class corresponds to a Hamiltonian cycle in a given graph G on 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 powers of 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.

AB - In this paper, we present some algebraic properties of a particular class of probability transition matrices, namely, Hamiltonian transition matrices. Each matrix P in this class corresponds to a Hamiltonian cycle in a given graph G on 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 powers of 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.

UR - http://www.scopus.com/inward/record.url?scp=84902300322&partnerID=8YFLogxK

U2 - 10.1007/s10479-014-1642-2

DO - 10.1007/s10479-014-1642-2

M3 - Article

SN - 0254-5330

VL - 243

SP - 19

EP - 35

JO - Annals of Operations Research

JF - Annals of Operations Research

IS - 1/2

ER -