Resonant Sets in Benzenoid Systems

Abstract

A benzenoid system $H$ is a finite 2-connected plane bipartite graph in which every interior face is bounded by a regular hexagon. A benzenoid system is called as cata-condensed if it is outer planar. A perfect matching is a set of independent edges which cover every vertex exactly once. A set of disjoint hexagons $S$ of a benzenoid system $H$ is a resonant set if the subgraph obtained from $H$ by deleting all vertices of hexagons in $S$ has a perfect matching. The resonant set is forcing if the subgraph has a unique perfect matching. In chapter 2, we define a forcing resonance polynomial of $H$ as $f(x)=\sum_{i=1}^{cl(H)} a_i x^i$ where $a_i$ is the number of distinct forcing resonant set of size $i$ and $cl(H)$ is the Clar number of $H$. We put all coefficients of this polynomial in a vector called as coefficient vector. We design a recursive algorithm to compute the forcing resonance polynomial of cata-condensed benzenoid systems with $n$ hexagons. The forcing resonance polynomial of $H$ can be used to enumerate the number of forcing resonant sets and its coefficient vector can be applied to predict the stability of benzenoid system more accurately than Clar number and Kekul\'e count, which are all traditional stability indicators of molecules. The coefficient vector is also better than HOMO-LUMO gap in terms of describing the structural characteristics of molecules. In chapter 3, we also design an algorithm to reconstruct the cata-condensed benzenoid systems in a specific case.

Forcing set is concept originated from the research on the application of Kekul\'e structure in the resonance theory in chemistry. This concept has been generalized to any graph $G$. For example, let $G$ be a graph with $m$ edges and $n$ vertices. A face of $G$ is forcing face if the subgraph of G obtained by deleting this face and all edges incident to this face has a unique perfect matching. In chapter 4, we give a forcing face detection algorithm based on a well-known unique perfect matching algorithm in $O(m^2\text{log}n^4)$ time. We also give an algorithm to construct graphs with unique perfect matching through odd bridges, inspired by reversely thinking this unique perfect matching algorithm. We present a forcing face construction algorithm based on the proposed unique perfect matching construction algorithm.