2016/07/19 by Kai Deng, Heping Zhang, Deng, Kai +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1607.05392
openalex publication_date 2016/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The anti-forcing number of a perfect matching M of a graph G is the minimal number of edges not in M whose removal to make M as a unique perfect matching of the resulting graph. The set of anti-forcing numbers of all perfect matchings of G is the anti-forcing spectrum of 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.