Some Studies On The Complete Forcing Numbers Of Graphs

The innate degree of freedom of Kekule structure was proposed by Klein and Randic in 1985 while studying the resonance structure of molecules.Harary et al.called it the forcing number of a perfect matching of a graph.A perfect matching M of a graph G is a set of disjoint edges that covers all its vertices.A forcing set of M is a subset of M contained in no other perfect matching of G.In 2004,Vukicevic and Sedlar introduced the concept of global(or total)forcing set of a graph G,which is defined as an edge subset S of G on which there are no two distinct perfect matchings coinciding.In 2015,combining the "forcing" and"global" ideas,Xu,Zhang and Cai proposed the concept of the complete forcing set of a graph G,which is defined as a subset of E(G)on which the restriction of each perfect matching M is a forcing set of M.The minimum possible cardinality of the complete forcing sets of G is called the complete forcing number of G.They proved that an edge subset S of G is a complete forcing set if and only if S intersects each perfect matching of any nice cycle of G.From this equivalent condition,we can see that a complete forcing set of a graph both forcing and anti-forcing each perfect matching.Chan et.al.showed that the complete forcing number of a catacondensed hexagonal system is equal to the number of hexagons plus the Clar number.Xu et al.obtained a certain explicit formula for the complete forcing numbers of primitive coronoids.But for pericondensed hexagonal systems or general graphs,there are few ways to compute their complete forcing numbers.In this thesis,we establish some methods of constructing a complete forcing set of a graph by elementary edge cut decomposition and 2-independent set respectively,by which we show that the complete forcing number of a graph is no more than 2 times its cyclomatic number and no more than the number of its edges minus its maximum degree.Meanwhile,we obtain some extremal graphs.Besides,we develop some lower bounds on the complete forcing numbers of plane elementary bipartite graphs in terms of the number of faces,matching number,Clar number and Fries number,respectively.Combining with the above upper and lower bounds,we obtain some expressions for the complete forcing numbers of some graphs of special types including complete multipartite graphs,cylinders and some pericondensed hexagonal systems.This thesis contains six chapters.In Chapter 1,we first introduce some basic concepts,terminologies and notations.And then we introduce the research background and progress about the forcing,anti-forcing problem of perfect matching and global forcing,complete forcing problem of graphs.Finally,we list the main results of this thesis.In Chapter 2,we first prove that the complete forcing number of a graph is equal to the sum of the complete forcing numbers of its elementary components.Next,using elementary edge cut decomposition,we establish a method of constructing a complete forcing set of a graph.In 2007,Doslic obtained that the global forcing number of a connected graph is at most its cyclomatic number.Motivated from this result,we obtain that the complete forcing number of a graph is no more than 2 times its cyclomatic number by elementary edge cut decomposition,and then characterize the matching covered graphs whose complete forcing numbers attain this upper bound and minus one,respectively.In Chapter 3,we use the nice cycle double cover to give a lower bound on the complete forcing numbers of graphs.Specially,we prove that the complete forcing number of a plane elementary bipartite graph is at least the number of its faces.Combining with the method of constructing a complete forcing set given in Chapter 2,we present closed formulas for the complete forcing numbers of wheels and cylinders.In Chapter 4,we first give a tight upper bound on the complete forcing number of a hexagonal system(HS)in terms of elementary edge-cut cover.And then we establish two lower bounds on the complete forcing numbers of normal HSs by the number of hexagons and matching numbers of its frame dual subgraphs,respectively.As applications,we give some explicit formulas for the complete forcing numbers of parallelogram,regular hexagon-and rectangle-shaped HSs.For a normal HS without 2 × 3 subsystems,from the view of dual graphs,we prove that its complete forcing number attains the second lower bound.Finally,we have a further discussion about the difference between the complete forcing numbers of normal HSs and the lower bound by matching numbers.In Chapter 5,we show that the complementary set of the set of edges incident with a 2-independent set of G is a complete forcing set.As applications,we give some expressions for the complete forcing numbers of complete multipartite graphs and graphs obtained from complete graph and complete bipartite graph by deleting the edge set of a subgraph whose maximum degree is at most 2 respectively,by showing that each sufficiently short cycle is a nice cycle.In Chapter 6,using the results shown by Shi et al.that the maximum forcing number and the maximum anti-forcing number of a(4,6)-fullerene graph is equal to its resonant number and Fries number respectively,we prove that the complete forcing number of a(4,6)-fullerene graph is at least the sum of its resonant number and Fries number.Moreover,we present some tubular(4,6)-fullerene graph whose complete forcing number attaining this lower bound.Finally,we conjecture that the complete forcing number of each(4,6)-fullerene graph attains the above lower bound.