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.