On the global forcing number of hexagonal systems

A global forcing set of a simple connected graph G with a perfect matching is a set of edges such that no two different perfect matchings of G coincide on it. The minimum size of global forcing sets of G is called the global forcing number of G. DoÅ¡lić proved that the global forcing number of a cata-condensed hexagonal system is equal to the number of its hexagons. In this paper, we consider normal hexagonal systems. By giving a criterion to determine if two adjacent hexagons of normal hexagonal systems form a nice subgraph, we establish a sharp lower bound on the global forcing number of normal hexagonal systems. For a kind of normal hexagonal systems called “divisible hexagonal systems”, we get a formula for the global forcing number and obtain a linear algorithm for finding a minimum global forcing set.