### G-93-04

# Hamiltonian Circuits, Hamiltonian Paths and Branching Graphs of Benzenoid Systems

## and BibTeX reference

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.

Published **January 1993**
,
27 pages