Extremal anti-forcing numbers of perfect matchings of graphs

preprint2016arXivOpen access

Abstract

The anti-forcing number of a perfect matching MM of a graph GG is the minimal number of edges not in MM whose removal to make MM as a unique perfect matching of the resulting graph. The set of anti-forcing numbers of all perfect matchings of GG is the anti-forcing spectrum of GG. 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.