Research On Forcing And Anti-forcing Problems Of Graphs

For any perfect matching M of graph G,it has a minimum subset S such that any other perfect matching of G does not contain S.The cardinality of such S is the forcing number of M.On the opposite side,E?G?\M has a minimum subset S such that G-S has a unique perfect matching M.The cardinality of such S is called the anti-forcing number of M.The minimum and maximum values of forcing?anti-forcing?numbers of all perfect matchings of G are called the minimum and maximum forcing?anti-forcing?numbers of G,respectively.The roots of the forcing and anti-forcing numbers of graphs can be found in an earlier chemical literature due to Randi?and Klein,under the name of the innate degree of freedom of a Kekuléstructure.In recent years,there are critical headway in theory and application.Adams et al.and Deng et al.showed that determining the forcing and anti-forcing numbers of a perfect matching of a bipartite graph are NP-complete,respectively.Deng and Zhang showed that the maximum anti-forcing number of a graph is no more than its cyclomatic number.For a hexagonal system H with a perfect matching,Xu et al.showed that the maximum forcing number of H equals to its Clar number,that is,the cardinality of a maximum set of the disjoint resonant hexagonal faces?a maximum set F of disjoint hexagonal faces such that H has a perfect matching M with each hexagon in F being M-alternating?.Lei et al.showed that the maximum anti-forcing number of H equals to its Fries number,that is,the cardinality of a maximum set of the resonant hexagonal faces.As an important chemical index,the Clar number and Fries number can be used to measure the stability of the hydrocarbons.For the molecular of novel spherical carbon clusters–fullerenes,Zhang et al.and Yang et al.discussed their minimum forcing and anti-forcing numbers,respectively.In this thesis,we first consider the new upper bound of the maximum anti-forcing number of graphs;we then discuss the maximum forcing and anti-forcing numbers of?4,6?-fullerenes,and study the maximum sets of the disjoint resonant hexagonal faces of?4,6?-fullerenes;we finally devote to characterize all fullerenes with the minimum forcing number 3.This thesis has five chapters as follows.In Chapter one,we introduce some basic concepts,terminologies and nota-tions.Then we introduce the background and research progress of the matching forcing and anti-forcing problems.In the end,we outline the main results of this thesis.In Chapter two,for a graph G with a perfect matching,we obtain a new tight upper bound of the maximum anti-forcing number of G dependent only on the order and size of G.If G has more edges,then this upper bound is better than the known upper bound.If a perfect matching M of G has the anti-forcing number attained this new upper bound,then we say M is a nice perfect matching.We characterize the nice perfect matchings of G,and show that the number of nice perfect matchings of G is the sum of the numbers of nice perfect matchings of each factor in a Cartesian decomposition of G.Besides,we demonstrate that each graph that has maximum anti-forcing number attained the new upper bound can be constructed from an edge by implementing two expansion operations.A?4,6?-fullerene graph is a 3-regular plane graph having only square faces and hexagonal faces.Extending the Clar number of a hexagonal system to a?4,6?-fullerene graph G,we obtain the resonant number of G,that is,the cardinality of a maximum set of disjoint resonant faces.Similarly,the Fries number of G is the cardinality of a maximum set of resonant faces.In Chapter three,for a?4,6?-fullerene G,we show that the maximum forcing number of G equals to its resonant number,the maximum anti-forcing number of G equals to its Fries number,which extend the known results for hexagonal systems with a perfect matching.Moreover,we obtain two formulas dependent only on the order of G to count the maximum forcing and anti-forcing numbers of G,respectively.A Clar formula of a?4,6?-fullerene is a maximum set of disjoint resonant hexagonal faces,its cardinality is denoted by Cl₆?G?.A Clar formula H of G and a perfect matching of G-V?H?constitute a Clar structure of G.In Chapter four,for a?4,6?-fullerene G,we first obtain formulas dependent only on the order of G to compute Cl₆?G?.Then the main works in this chapter is to characterize all the Clar formulas of G.Applying this result,we finally get formulas to compute the numbers of Clar formulas and Clar structures of G,which only depend on the order of G and the number of the fixed subgraphs of G that is easy to identify.A fullerene graph is a 3-regular plane graph having only pentagonal faces and hexagonal faces.For a fullerene G,Zhang et al.showed that the minimum forcing number of G is no less than 3.Then they posed a question to charac-terize all fullerenes with the minimum forcing number 3.We know that there is only one fullerene with order 24,denoted by F₂₄.In Chapter five,we obtain a unique counter-example,that is,we find F₂₄has the minimum forcing number 2.Applying the known results of cyclic 5-edge-cuts,cyclic 6-edge-cuts and cyclic 7-edge-cuts of fullerenes,by extending subgraphs,we characterize all the fullerenes with the minimum forcing number 3.Particularly,except for F₂₄,each fullerene with anti-forcing number 4 has the minimum forcing number 3.