Recognizing Kekuléan benzenoid systems byC-P-V path elimination

In this paper, we define the concept of a canonicalP-V pathP(p _i– _i ) on the boundary of a benzenoid systemH, and prove thatH has a Kekulé structure if and only ifH-P(p _i–v _i) has a Kekulé structure, whereH-P(p _i–v _i) is the graph obtained fromH by deleting the vertices onP(p _i–v _i) . It is also proved that there are at least two canonicalP-V paths in a benzenoid system. By the above results, we give an efficient and simple algorithm, called the canonicalP-V (C-P-V) path elimination, for determining whether or not a given benzenoid systemH has Kekulé structures. IfH is Kekuléan, the algorithm can find a Kekulé structure ofH.Supported by NSFC.