Studies On Matching Forcing Spectrum And Matching Anti-forcing Spectrum Of Graphs

The forcing number of a perfect matching M of a graph G is the smallest number of M-matched edges that can determine M. The concept of the forcing number of a perfect matching of a graph was originally introduced by Harary et al. The same idea appeared in earlier chemical literatures due to Klein and Randi′c under the name of the innate degree of freedom of a Kekul′e structure, which plays an important role in the resonance theory in chemistry. The collection of forcing numbers of all perfect matchings of G is called the forcing spectrum of G, the smallest integer of the forcing spectrum of G is called the forcing number or minimum forcing number of G, the largest integer is called the maximum forcing number of G. On the opposite side, the anti-forcing number of M of G is the minimal number of edges not in M whose removal makes M a unique perfect matching of the resulting graph. The set of anti-forcing numbers of all perfect matchings of G is called the anti-forcing spectrum of G, the smallest number of the anti-forcing spectrum of G is called the anti-forcing number or minimum anti-forcing number of G, the largest number is called the maximum anti-forcing number of G.This thesis contains six chapters. In Chapter 1, we ?rst introduce some basic de?nitions and notations of graph theory. Then we introduce the research background and development of the matching forcing problem and matching anti-forcing problem.Finally, we list the main results of this thesis.In Chapter 2, we prove that the forcing spectrum of a hexagonal system H with forcing number 1 is either the integer interval [1, cl(H)] from 1 to its Clar number cl(H) or [1, cl(H)] \ {2}. We also give a su?cient condition for the forcing spectrum of a hexagonal system to have no gaps.In Chapter 3, we ?rst show that any ?nite set of positive integers can be the anti-forcing spectrum of a graph. We also characterize the plane elementary bipartite graphs with anti-forcing number 1. Then we prove that the maximum anti-forcing number of a graph is at most its cyclomatic number, and the extreme graphs with the maximum anti-forcing number achieving the upper bound are characterized. Finally we show that determining the anti-forcing number of a perfect matching of a bipartite graph with maximum degree 4 is an NP-complete problem.In Chapter 4, we prove that there is at most one gap between any two consecutive numbers in the anti-forcing spectrum of a hexagonal system, and the anti-forcing spectrum of any catacondensed hexagonal system has no gaps.In Chapter 5, we show that the anti-forcing spectra of two types of constructable hexagonal systems are integer intervals. As a consequence, the anti-forcing spectrum of a hexagonal system with forcing number 1 has no gaps.In Chapter 6, we show that the anti-forcing spectrum of an even polygonal chain has no gaps, and linear algorithms are obtained to compute the minimum and maximum anti-forcing numbers of an even polygonal chain. So the anti-forcing spectrum of an even polygonal chain can be determined in linear time.