2014/06/15 by Hongchuan Lei, Lei, Hongchuan, Yeong‐Nan Yeh +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1406.3796
openalex publication_date 2014/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We define the anti-forcing number of a perfect matching M of a graph G as the minimal number of edges of G whose deletion results in a subgraph with a unique perfect matching M, denoted by af(G,M). The anti-forcing number of a graph proposed by Vukičević and Trinajstić in Kekulé structures of molecular graphs is in fact the minimum anti-forcing number of perfect matchings. For plane bipartite graph G with a perfect matching M, we obtain a minimax result: af(G,M) equals the maximal number of M-alternating cycles of G where any two either are disjoint or intersect only at edges in M. For a hexagonal system H, we show that the maximum anti-forcing number of H equals the Fries number of H. As a consequence, we have that the Fries number of H is between the Clar number of H and twice. Further, some extremal graphs are discussed.