Hamiltonian circuit

A Hamiltouian path is a path in which all vertices of the graph must be visited once and the beginning and the end are different. A Hamiltonian circuit is a path in which all vertices of the graph must be visited once, starting and ending on the same vertex. 

Angluin D, Valiant LG (1979) Fast probabilistic algorithms for hamiltonian circuits and matchings. Journal of Computer Science and Systems 18 155... 

A Hamiltonian circuit is a closed chain drawn on a (non-oriented) lattice, so as to pass once and only once on each lattice site. A Hamiltonian walk is an open chain drawn on a (non-oriented) lattice, so as to pass once and only once on each lattice site. 

First, we shall consider the case where every Hamiltonian circuit is drawn on a given rectangular lattice and we shall study how the number of circuits increases when the size of the lattice grows. The result is probably rather general and in this case the boundary conditions play a minor role. However, in certain cases, the boundary conditions may be important and this statement will be justified by considering certain hexagonal lattices and the Hamiltonian walks drawn on them. Finally, note that problems concerning Hamiltonian circuits are also studied, in Chapter 11, Section 6, in connection with field models . 

Hamiltonian circuits on a square lattice with a rectangular shape... 

Let us consider a square lattice with M columns and N lines, i.e. MN sites (see Fig. 3.8). Let UM N be the number of Hamiltonian circuits that can be drawn on the lattice. If M and N are uneven UM N = 0 for the following reason. On the one hand, the number of segments on the circuit is equal to the number of sites, i.e. MN. On the other hand, the circuit is made up of an even number of vertical steps and of an even number of vertical steps consequently, the total number of segments (elementary steps) is even. Thus MN must be even, and this property will be assumed in what follows. In this section, we show that In UMtN/MN has a limit when M and N become infinite (MN = even). 

Let us start by showing that nUU N/MN is bounded. First, we observe that two oriented circuits can be associated with each Hamiltonian circuit. Then, let us start from a corner we see that at every step, we can choose between three directions at most. Thus we have... 

Fig. 3.8. Hamiltonian circuit on a square lattice made of M columns and N lines (here M = 10, N = 6).

Fig. 3.9. By starting from one circuit (M, N), it is possible to make two Hamiltonian circuits (M, N + 2).

Hamiltonian circuit and Hamiltonian walks on a layered hexagonal lattice... 

At first, we observe that it is not possible to draw any Hamiltonian circuit on the lattice to get this result, we have only to observe that such a circuit must pass through all the sites of the external layer and that this is not compatible with the exploration of the interior points. 

Hamiltonian circuits are a mathematical idealization of polymer melts. General considerations concerning these circuits are given here. Exact results, in two dimensions will be found at the end of the next chapter. 

An approximate value of the number of Hamiltonian circuits covering a homogeneous lattice... 

The constraint all-different is the most important of the group of so-called symbolic constraints. The rest of this group is not explained here, only the names are given count, element, relation, assignment, circuit (Hamiltonian circuit), and constraints specifically designed for scheduling problems serialized, cumulative, disjointl, and disjoint 2. ... 

P. Hansen, Hamiltonian circuits, Hamiltonian paths and branching graphs of benzenoid systems, J. Math. Chem. 17 (1995) 15-33. 

J. Lederberg, Hamiltonian circuits of convex trivalent polyhedral (up to 18 vertices). Am. Math. Monthly 74 (1967) 522-527. 

FIGURE 14.5 Buckminsterfullerene displaying Hamiltonian circuit as drawn by Randic. (Reproduced from On history of the Randic index and emerging hostility toward chemical graph theory, MATCH Commun. Math. Comput. Chem., 2008.)... 

A similar analysis of Hamiltonian circuits generated on cubic lattices of dimensions 2 x p x n yields the equation... 

---