The Relationship Between Global Forcing Number And Maximum Anti-forcing Number Of A Graph

In this paper,we mainly discuss about the relationship between global forcing number and anti-forcing number of a graph.This paper is divided to four parts.We introduce the related concepts of graphs,the research background and progress of the "forcing" problem and the main conclusions of this paper in chapter 1.For any perfect matching M of G,we call S,the subset of the edges of G,is an anti-forcing set of M of G,if G-S has a unique perfect matching.The cardinality of the minimum anti-forcing set of M is called the anti-forcing number of M,denoted by af(G,M).The minimum(or,maximum)anti-forcing number corresponding to all perfect matches of G is called the minimum(or,maximum)anti-forcing number of G,denoted by af(G)(or Af(G).We call an edge subset S of G is a global forcing set of G,if there is no nice cycles of G in G-S.The cardinality of the minimum global forcing set of G is said to be the global forcing number of G,denoted by gf(G).We compare global forcing number of a graph with its maximum forcing number and anti-forcing number respectively in chapter 2.The global forcing number of the graph is always bigger than or equal to its maximum forcing number.But it could be smaller than its maximum anti-forcing number.For a graph,which contains no two disjoint odd cycles,its global forcing number of a graph is greater than or equal to its maximum anti-forcing number.Naturally,the conclusion is true for a bipartite graph.We study the difference between the global forcing number and the maximum anti-forcing number of a graph in chapter 3.For a connected graph G with 2n vertices,we have-1/2(n2-n-2)?gf(G)-Af(G)?<(n-1)(n-2).Moreover,if G is a bipartite graph,then 0<gf(G)-Af(G)?1/2(n-1)(n-2).We call a graph G is elementary,if the subgraph induced by all edges,which belong to some perfect matching of G,is connected.When the number of vertices of a graph is not limited,we prove that for any positive integer k,there is an elementary graph G such that gf(G)-Af(G)=-k.In chapter 4,we mainly relate the problem of "forcing" to the tight cut of graphs.If E(V1,V2)is a non-trivial tight cut of G,then gf(G1)+gf(G2)-2|E(Vi,V2)|+2?<gf(G)?gf(G1)+gf(G2),where Gi is obtained from G by shrinking Vi into a vertex vi,i.e.Gi=G/Vi,i= 1,2.For the forcing number,anti-forcing and complete forcing number,the similar conclusions are established.