Determinants and longest cycles of graphs

Ejov, Vladimir, Filar, Jerzy A. , Murray, Walter and Nguyen, Giang T. (2008) Determinants and longest cycles of graphs. SIAM Journal on Discrete Mathematics, 22 3: 1215-1225. doi:10.1137/070693898

Author Ejov, Vladimir
Filar, Jerzy A.
Murray, Walter
Nguyen, Giang T.
Title Determinants and longest cycles of graphs
Journal name SIAM Journal on Discrete Mathematics   Check publisher's open access policy
ISSN 0895-4801
Publication date 2008-01-01
Sub-type Article (original research)
DOI 10.1137/070693898
Open Access Status Not yet assessed
Volume 22
Issue 3
Start page 1215
End page 1225
Total pages 11
Place of publication Philadelphia, PA, United States
Publisher Society for Industrial and Applied Mathematics
Language eng
Formatted abstract
We consider the Hamiltonian cycle problem on a given graph G. With such a graph we can associate a family F of probability transition matrices of Markov chains whose entries represent the probabilities of traversing corresponding arcs of the graph. When the underlying graph is Hamiltonian, we show the transition probability matrix induced by a Hamiltonian cycle maximizes-over F-the determinant of a matrix that is a rank-one correction of the generator matrix of a Markov chain. In the case when the graph does not possess a Hamiltonian cycle, the above maximization yields a transition matrix of a chain with a longest simple cycle (in G) comprising that chain's unique ergodic class. These problems also have analogous eigenvalue interpretations.
Keyword Hamiltonian cycle
Markov chains
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Non-UQ

Document type: Journal Article
Sub-type: Article (original research)
Collection: School of Mathematics and Physics
Version Filter Type
Citation counts: Scopus Citation Count Cited 5 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Fri, 20 Jan 2017, 23:32:34 EST by Kay Mackie on behalf of Learning and Research Services (UQ Library)