The anti-forcing number of a perfect matching   M     M        of a graph   G     G        is the minimal number of edges not in   M     M        whose removal to make   M     M        as a unique perfect matching of the resulting graph. The set of anti-forcing numbers of all perfect matchings of   G     G        is the anti-forcing spectrum of   G     G       . In this paper, we characterize the plane elementary bipartite graph whose minimum anti-forcing number is one. We show that the maximum anti-forcing number of a graph is at most its cyclomatic number. In particular, we characterize the graphs with the maximum anti-forcing number achieving the upper bound, such extremal graphs are a class of plane bipartite graphs. Finally, we determine the anti-forcing spectrum of an even polygonal chain in linear time.
['Kai Deng', 'Heping Zhang']
Extremal anti-forcing numbers of perfect matchings of graphs