In this paper, we present the molecular structure of benzene as a regular hexagonal ring and an isomorphic hexagonal lattice, a molecular structure introduced by Merrifield-Simmons (MS) in 1989. The MS index, a topological index used in mathematical chemistry, is the number of independent sets of a graph G. This index plays a crucial role in our understand ing of complex molecular structures. The strategy to compute the MS index involves the construction of a Hamiltonian trajectory in the input graph. These structures are discussed in fields such as theoretical and computational chemistry. Therefore, we propose a novel branch and bound method for counting independent sets on polygonal benzenoid meshes, highlighting its importance in the study of the analysis of complex molecular structures and its applicability in interdisciplinary scientific fields.

Benzenoid, Independent Sets, Hamiltonian Path