Hamiltonian path

If the number of vertices is even, then an evidently sufficient condition for the existence of Kekule structures of a benzenoid system is the existence of a Hamiltonian path [17]. As a corollary, all catacondensed benzenoid systems are Kekulean [18]. But the condition is not necessary. A Kekulean benzenoid system with no Hamilton path is shown in Fig. 4. 

Fig. 29 An allocation of double vs. single bonds that forms a Hamiltonian path in a titanium-zirconium metcar...

Finding the necessary and sufficient conditions for the existence of a Hamiltonian path ( = path which embraces all the vertices) of a benzenoid system seems to be a much more difficult task. Kirby [12,13] calls benzenoid systems possessing a Hamiltonian path traceable . Of course, Hamiltonian benzenoids are necessarily traceable, but the reverse is not true. There exist many traceable non-Hamiltonian benzenoids, e.g. the systems 7,8,9, and 13 in Fig. 1. Two Hamiltonian paths of the system 9 are indicated in the diagrams below ... 

Figure 8. A directed graph with a unique Hamiltonian path, where circles represent vertices (cities) and arrows represent edges (routes).

Seminal work by Adleman demonstrated that molecular biological methods could be successfully employed to solve a mathematical problem [84, 85]. The problem he solved was a Hamiltonian path problem, in common parlance referred to as a travelling salesman problem. This is a hard computational problem for which no satisfactory algorithm is known allowing solution with electronic computers in polynomial time [86]. The potential of this DNA-based methodology relies on the inherent parallelism a DNA molecule affords. 

The solution to Adleman s problem (Figure 8) is the correct combination of routes between several vertices (or cities), fulfilling several criteria. These are that the starting and finishing cities in the directed graph are defined, each city must be visited, each city can only be visited once, and there is a defined set of one-way edges (or routes) connecting different cities. A Hamiltonian path may not exist, if all the above criteria cannot be satisfied. 

Disappointingly, we found that a 2-opt optimization of the greedy TSP-tour leads to only 0.3% improvement (Table 1). We tried a few approaches to further improve the TSP solution (or to verify its proximity to the optimal solution), in particular, solving minimum length cycle cover problem with further merging of cycles in the cover into a hamiltonian path. A cycle cover is a set of (simple) cycles such that each vertex in the graph is contained in exactly one cycle. The... 

A Hamiltonian 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. 

Let us consider the conformation of a single chain in the special case of a disordered state with no vacancy. Fixing Ao=0, Ai = 1 in the theory developed above, the number Wh (n) of paths that visit all lattice points (cells) without overlap, referred to as Hamiltonian path, is found [21]. Within the theoretical framework (2.146) described in the preceding sections, the entropy of Hamiltonian paths is estimated by... 

The following are known regarding the number of Hamiltonian paths ... 

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

The remaining 19 graphs of Figure 11.12 have Hamiltonian paths. Let us propose three problems relating to resonance graphs ... 

Try to characterize peri-condensed benzenoid graphs that have a Hamiltonian path. Problem 17... 

Baumgardner, Jordan, et al. (2009). Solving a Hamiltonian Path Problem with a Bacterial Computer. Journal of Biological Engineering. Vol. 3 11. 

Storage, though, is all very well, but how can the information be written and retrieved An exploratory experiment, based, to be sure, on laborious biochemistry, was performed by L. M. Adleman more than a decade ago. As a first demonstration of the watery DNA computer in action he chose to solve a simple form of what mathematicians know as the Hamiltonian path, or travelling salesman problem—how, starting from city A, to travel to each of a succession of other cities, terminating at city Z, without ever retracing your path. A formal solution to this ancient mathematical teaser was worked out in the early nineteenth century by two mathematicians. Sir William Rowan Hamilton in Ireland and Thomas Kirkman in England. With their aid an answer can be easily found if the number of cities is small, but if there are many it requires an enormous amount of computer time. 

Adleman used DNA computation to solve a small instance of the Hamiltonian path problem. This is a notorious hard computational problem as it is consid-... 

Fig. 2.11 The instance of the Hamiltonian Path Problem which Adleman solved by DNA computation. The question is whether or not a path exists which is composed of the given unidirectional edges (arrows), starts at 0 and ends at 6, and visits each of the vertices (numbered circles) exactly once. (As one can easily verify, the answer is yes. The path connects the vertices in numerical order.)...

Adleman designed the simple instance of the Hamiltonian path problem with 7 vertices and 13 edges shown schematically in Fig. 2.11. The question is Is there a route from vertex 0 (vin) to vertex 6 (vout) using only the unidirectional lihks indicated by arrows and visiting every vertex exactly once As one can easily verify, there is a unique solution 0-1-2-3-4-5-6. 

---