Groupe d’études et de recherche en analyse des décisions

Hamiltonian Circuits, Hamiltonian Paths and Branching Graphs of Benzenoid Systems

Pierre Hansen et Maolin Zheng

A benzenoid system H is a finite connected subgraph of the infinite hexagonal lattice without cut bonds and non-hexagonal interior faces. The branching graph G of H consists of all vertices of H of degree 3 and bonds among them. In this paper, the following results are obtained: (1) A necessary condition for a benzenoid system to have a Hamiltonian circuit. (2) A necessary and sufficient condition for a benzenoid system to have a Hamiltonian path. (3) A characterization of connected subgraphs of the infinite hexagonal lattice which are branching graphs of benzenoid systems. (4) A proof that if a disconnected subgraph G of the infinite hexagonal lattice given along with the positions of its vertices is the branching graph of a benzenoid system H, then H is unique.

, 27 pages