Hamiltonicity as a spectral property
(J Filar and V Ejov with P Zograf)
The stochastic approach to the Hamiltonian cycle problem that puts
randomised weights (probabilities) on various arcs of a graph combined with
non-convex optimisation or with a type of branch and bound method, generally
leads to a reduced graph by deletion of certain arcs.
Such an arc elimination procedure can be performed in succession and thus fits the theory of Graph Perturbations that it concerned with changes in various structures corresponding to the graphs that result from local modifications such as the addition or deletion of a vertex or an arc.
An important structure in the perturbation theory is the spectrum of the graph (i.e. the eigenvalues of the graph's adjacency matrix). This leads to the natural questions: Are there properties of a graph's spectrum that are responsible for the Hamiltonicity? Are iso-spectral graphs simultaneously Hamiltonian or non-Hamiltonian?
For this spectral approach to the Hamiltonicity of graphs we plan to exploit the novel insight (due to Peter Zograph) that adapts Ihara-Selberg trace formula for regular graphs.
This topic is made up of a component in Jerzy Filar’s recently awarded ARC Discovery grant (with Jacek Gondzio and Peter Zograf).