Recognition of essentially disconnected benzenoids (Q1210271)

A benzenoid, or a benzenoid system, is a connected planar graph whose every interior face is a regular hexagon. A peak (resp. valley) of a benzenoid is a vertex which lies above (resp. below) of all of its first neighbors. A Kekuléan benzenoid is a benzenoid with at least one perfect matching. An essentially disconnected benzenoid is a Kekuléan benzenoid which has some fixed bonds. Essentially disconnected benzenoids have proved to be very useful in certain enumeration techniques for perfect matching. Hence the problem of recognizing essentially disconnected benzenoids has attracted many researchers and several scientific papers have appeared. In [Match 25, 71 (1990)] the authors developed a method called the \(g\)- cut method to determine whether or not a given benzenoid is essentially disconnected. The method is based on the following theorem of the authors in [Match 25, 71 (1990)]. Theorem 3. Let \(H\) be a Kekuléan benzenoid. Then \(H\) is essentially disconnected if and only if there is at least one horizontal \(g\)-cut (for some position) such that \(s=t\) holds, where \(s\) is the number of edges intersected by the horizontal line segment \(P_ 1P_ 2\), \(t\) is the difference between the number of peaks and the number of valleys lying in the upper bank of the horizontal \(g\)-cut. The main purpose of this paper is to give a new criterion of essentially disconnected benzenoids which is better than that one described in Theorem 3, and to develop a rapid way to recognize essentially disconnected benzenoids based on an algorithm which enables us to determine the correspondence between the set of peaks and the set of valleys.