Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949470 | Discrete Applied Mathematics | 2017 | 10 Pages |
Abstract
An edge of a graph G is called an anti-forcing edge (or forcing single edge) if G has a unique perfect matching not containing this edge. It has been known for two decades that a hexagonal system has an anti-forcing edge if and only if it is a truncated parallelogram. A connected subgraph G of a hexagonal system is called a single coronoid system if G has exactly one non-hexagonal interior face and each edge belongs to a hexagon of G. In this paper, we show that a single coronoid system with an anti-forcing edge can be obtained by gluing a truncated parallelogram with a generalized hexagonal system which has a unique perfect matching and can be obtained by attaching two additional pendant edges to a hexagonal system, and the latter can be constructed from one hexagon case by applying five modes of hexagon addition. Such graphs are half essentially disconnected coronoid systems in the rheo classification. So computing the number of perfect matchings of such graphs is reduced to that of two hexagonal systems.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Xiaodong Liang, Heping Zhang,