Hamiltonian cycle curves in the space of discounted occupational measures

Jerzy A. Filar () and Asghar Moeini ()
Additional contact information
Jerzy A. Filar: Flinders University
Asghar Moeini: Flinders University

Annals of Operations Research, 2022, vol. 317, issue 2, No 13, 605-622

Abstract: Abstract We study the embedding of the Hamiltonian Cycle problem, on a symmetric graph, in a discounted Markov decision process. The embedding allows us to explore the space of occupational measures corresponding to that decision process. In this paper we consider a convex combination of a Hamiltonian cycle and its reverse. We show that this convex combination traces out an interesting “H-curve” in the space of occupational measures. Since such an H-curve always exists in Hamiltonian graphs, its properties may help in differentiating between graphs possessing Hamiltonian cycles and those that do not. Our analysis relies on the fact that the resolvent-like matrix induced by our convex combination can be expanded in terms of finitely many powers of probability transition matrices corresponding to that Hamiltonian cycle. We derive closed form formulae for the coefficients of these powers which are reduced to expressions involving the classical Chebyshev polynomials of the second kind. For regular graphs, we also define a function that is the inner product of points on the H-curve with a suitably defined center of the space of occupational measures and show that, despite the nonlinearity of the inner-product, this function can be expressed as a linear function of auxiliary variables associated with our embedding. These results can be seen as stepping stones towards developing constraints on the space of occupational measures that may help characterize non-Hamiltonian graphs.

Keywords: Hamiltonian cycle; Markov decision process; Occupational measure; Chebyshev polynomial; Regular graph (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-015-2030-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:317:y:2022:i:2:d:10.1007_s10479-015-2030-2

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

DOI: 10.1007/s10479-015-2030-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 ().