Abstract
We present a method for computing the Merrifield-Simmons index on some basic graphs. For example, our proposal works on paths, simple cycles, trees, and we show that the method can be extended to process benzenoid systems \(H_{r,t}\) with a total of \(r
\cdot t\) hexagons. In the case of benzenoid systems, our method consists of performing a linear-time Hamiltonian walking on an isomorphic hexagonal grid from \(H_{r,t}\,\), at the same time that the number of independent sets are being
computed incrementally. Our method improves the asymptotic behavior of the time-complexity with respect to the transfer matrix method, which is the classic method for computing the Merrifield-Simmons index on grid graphs, even for benzenoid
systems.
