Hamiltonian circuits, Hamiltonian paths and branching graphs of benzenoid systems

摘要

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.