(c) Larry Ewing, Simon Budig, Garrett LeSage
1994 .
Computer Science Department
PetrSU | Software projects | AMICT | Staff | News archive | Contact | Search

Evaluation of the connectivity constant for the number of Hamiltonian circuits on triangular grid graphs

A. Karavaev (Petrozavodsk State University, Russia)

It is common to evaluate the number of Hamiltonian circuits HN on large grid graphs with the help of the formula HN ~ μP∙κN , where value P depends on the number of nodes, laying on a grid’s “border,” while κ is a connectivity constant of the grid. The connectivity constant is interesting for modeling conformations of full-packed macromolecules, because this value is connected with entropy of one node of a grid.

Due to computational complexity of enumerations of Hamiltonian circuits, a connectivity constant κ is computed by reducing a discrete problem to continuous one in physical papers. It is the typical technique of using standard O(n) model. In this model an initial graph is approximated by a regular graph. This way one can get κ=q/e, where q is a degree of each node of the regular graph and it doesn’t depend on topological structure of the graph.

Comparison of the result of standard O(n) model methods and exact enumerations methods on rectangular lattices Pm×Pn and cylinders Cm×Pn (with q=4) gave wonderful agreement on values of κ with accuracy of 0.09%. At the same time there are no papers about accuracy of the standard O(n) model for other grid graph families.

In this paper we consider two-dimensional triangular grid graphs, bordered by m×n parallelogram (with q=6). We got value κ=2.095±0.005. This result differs from the result of the standard O(n) model 6/e≈2.21 by 5.7%. This result implies limitations of the standard O(n) model.