On the global forcing number of hexagonal systems ?
A global forcing set of a simple connected graph G G with a perfect matching is a set of edges such that no two different perfect matchings of G G coincide on it. The minimum size of global forcing sets of G G is called the global forcing number of G G . Doli? 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.
global forcing number hexagonal system perfect matching divisible hexagonal system