Research On Forcing And Anti-forcing Polynomials For Some Classes Of Graphs

Klein and Randic and Harary et al.proposed the forcing number of a perfect matching M of a graph G in chemical and mathematical literatures respectively,which is the minimal number of edges of M that are contained in no other perfect matchings of G.The anti-forcing number of M is the minimal number of edges of G not in M whose deletion results in a subgraph with a unique perfect matching M.In general,determining the forcing and anti-forcing numbers of a perfect matching of a bipartite graph are both NP-complete problems.Researches showed that for a hexagonal system,its maximum forcing number equals its Clar number,its maximum anti-forcing number equals its Fries number,and the two indices both can measure its stability.In a general graph,the forcing number of a perfect matching is no less than the maximum number of disjoint alternating cycles,and Guenin and Thomas showed that there is a equivalence relation between the above two indices for a bipartite graph which contains no even subdivision of K3,3 or the Heawood graph as a nice subgraph;the anti-forcing number of a perfect matching is no less than the maximum cardinality of compatible alternating sets,and there is a equivalence relation between the above two indices for a bipartite graph which contains no subdivision of K3,3.In recent years,a lot of studies on the maximum and minimum forcing and anti-forcing numbers,and forcing and anti-forcing spectra have been considered.However,calculating the number of perfect matchings with the same forcing and anti-forcing numbers is at the starting stage.On this basis,we propose the forcing polynomial of a graph G,namely a counting polynomial for perfect matchings with the same forcing number,and obtain some important topological indices from it.For example,the sum over the coefficients of the forcing polynomial is the perfect matching count of G,calculating the derivative and letting the independent variable be 1 gives the sum over the forcing numbers of all perfect matchings of G,the quotient of the two indices is the average forcing number of G.We can also get the maximum and minimum forcing numbers and the forcing spectrum of the graph from its forcing polynomial.Similarly,Hwang et al.proposed the anti-forcing polynomial of a graph as a counting polynomial for perfect matchings with the same anti-forcing number,and we can also get a series of topological indices from it.In solving the forcing and anti-forcing polynomials of a graph,we first give a recurrence relation by analyzing the combinatorial structure,then give an explicit expression by combinatorial calculation.An outline of the paper is as follows.In Chapter 1,we introduce two important classes of plane bipartite graphs,and the research background of forcing and anti-forcing numbers.In Chapter 2,we introduce the matching forcing polynomial of a graph and obtain some properties.We give a recursive expression of the forcing polyno-mial for catacondensed hexagonal systems.In particular,we derive an explicit expression of the forcing polynomial for zigzag hexagonal chains by generating function,together with the asymptotic behavior for their average forcing number,from which we get the degree of freedom of such graphs presented by Klein and Randic.In Chapter 3,we obtain a recurrence relation and an explicit expression of the forcing polynomial for benzenoid parallelograms,together with their maximum and minimum forcing numbers and the asymptotic behavior for their average forcing number as one variable approaches infinity.Moreover,we give their forcing polynomial by a combinatorial calculation.In Chapter 4,we study the matching anti-forcing polynomial of a graph.We obtain a recurrence relation of the anti-forcing polynomial for hexagonal systems with forcing edges,from which we get the continuity of the anti-forcing spectrum of such graphs presented by Deng and Zhang.In particular,we derive an explicit expression of the anti-forcing polynomial for benzenoid parallelograms,together with their maximum and minimum anti-forcing numbers and the asymptotic be-havior for their average anti-forcing number as one variable approaches infinity.In Chapter 5,we give the forcing and anti-forcing polynomials for 2×n grids and 3 × 2n grids,together with their forcing and anti-forcing spectra.In Chapter 6,we list the forcing polynomials of generalized Petersen graph P(n,2)for 3 ? n ? 36 and derive the forcing spectrum of P(n,2)for n ? 37,which is[[n/12]+ 1,[n+3/7]+?(n)]? |[n-2/6],[n/4]],where ?(n)= 1 if n?3(mod 7),and ?(n)= 0 otherwise,namely the union of two integer intervals.