Recognition of essentially disconnected benzenoids
type: Item
instance of: scholarly article
title: Recognition of essentially disconnected benzenoids
zbMATH Open document ID: 0770.05091
DOI: 10.1007/BF02006746
published in: Acta Mathematicae Applicatae Sinica. English Series
publication date: 1993-05-24T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 92E10
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 178022
zbMATH Keywords: benzenoid
zbMATH Keywords: connected planar graph
zbMATH Keywords: regular hexagon
zbMATH Keywords: peak
zbMATH Keywords: valley
zbMATH Keywords: Kekulán benzenoid
zbMATH Keywords: perfect matching
zbMATH Keywords: essentially disconnected benzenoid
zbMATH Keywords: algorithm
author: Rongsi Chen
author: Sven J. Cyvin
author: B. N. Cyvin
MaRDI profile type: Publication
cites work: When each hexagon of a hexagonal system covers it
cites work: Q4036018
cites work: Perfect matchings in hexagonal systems
full work available at URL: https://doi.org/10.1007/bf02006746
OpenAlex ID: W2352416910
description: scientific article; zbMATH DE number 178022