Research On Forcing,Anti-Forcing And Global Forcing Problems Of Perfect Matchings Of Graphs

How to select as few edges as possible that meet certain specific conditions to de-termine perfect matchings of a graph is a so-called matching forcing problem of graphs.A perfect matching of a graph is a set of disjoint edges covering all its vertices,which is chemically called Kekuléstructure.The term of the forcing number of a perfect match-ing of a graph was given by Harary et al.,which is essentially the concept of the inner degree of freedom of a Kekuléstructure proposed by Randi?and Klein when study-ing the molecular resonance structure.In 2016,H.Zhang,Y.Ye and H.Lei proposed the concept of the anti-forcing number of a single perfect matching in a graph.For a perfect matching M of a graph G,if an edge subset S of M（or E（G）-M）satisfies that G-V（S）（or G-S）has a unique perfect matching M-S,then we call S a forcing set（or an anti-forcing set）of M.Vuki?evi?and Sedlar proposed the concept of global forcing set of a graph without relying on a single perfect matching,which is an edge subset that distinguishes all different perfect matches of a graph.The global forcing number of a graph G refers to the size of its minimum global forcing set,which is recorded as gf（G）.This thesis first generalizes the conclusion that the global forcing number of a bi-partite graph is greater than or equal to the maximum anti-forcing number,and focuses on characterizing Birkhoff-von Neumann graphs with equal values（i.e.,graphs that do not contain nice disjoint odd cycle pairs,abbreviated as BV graphs）.Recently T.Do?li?pointed out that fullerene graphs are not BV graphs,We further study the nice disjoint pentagon pairs in fullerene graphs,and solve 4 open problems he raised.For another class of chemical graphs,say hexagonal systems,we obtain the value of the minimum（anti-）forcing number and the conclusion that the forcing spectrum of each convex hexagonal systems is continuous.At the same time,we also obtain that its anti-forcing spectrum is not necessarily continuous,and give sufficient conditions for continuous and non-continuous cases,respectively.Finally,in order to deeply study the minimax results of anti-forcing numbers,we transformed the related problems of bipartite graphs into the cycle packing problem of directed graphs,and discovered and characterized two types of directed graphs that do not satisfy the cycle packing proper-ties.This thesis is divided into six chapters.In Chapter 1,we will first introduce some basic concepts,terms and symbols used in this thesis?then the research background and progress of forcing,anti-forcing and global forcing are described?finally,the main conclusions of this thesis are shown.In Chapter 2,we extend that a bipartite graph G with perfect matchings satisfies gf（G）≥Af（G）to BV graphs and bricks without even subdivisions of the triangular prism as its nice subgraphs.In the process of characterizing a graph whose global forc-ing number is equal to the maximum anti-forcing number,we propose the concept of nice balanced graph.Let G be a graph with perfect matchings.A subgraph H of G is called nice,if G-V（H）has a perfect matching.A graph is called nice balanced,if for every nice subgraph with perfect matchings,its global forcing number is equal to its maximum anti-forcing number.Applying the ear decomposition theorem,we find 29BV graphs that do not satisfy this equation（4 of which are bipartite graphs）.After ex-cluding the even subdivisions of these 29 graphs as nice subgraphs,the characterization of nice balanced BV graphs is obtained.In Chapter 3,we solved four open problems about fullerene graphs raised by Do?li?.Do?li?pointed out that any fullerene graph is not BV graph,i.e.contains nice pair of disjoint odd cycles.We prove that the“odd cycles”in the conclusion can be re-placed by“pentagons”.When considering fullerenes with at most two pentagons adja-cent to each pentagon,we construct only one fullerene with 36 vertices,which contains a non-nice pair of disjoint pentagon.As a corollary,each pair of disjoint pentagons of IPR fullerenes forms a nice subgraph.In Chapter 4,we study hexagonal systems,i.e.2-connected planar graphs with every inner face being a regular hexagon.For a convex hexagonal system with perfect matching O（n₁,n₂,n₃）（where n₁≤n₂≤n₃）,we use the perfect path system to prove that its minimum forcing number and minimum anti-forcing number are equal to n₁.By the above method,we further obtain the minimum forcing number and the minimum anti-forcing number of a 3-divisible monotonic hexagonal system.In particular,we obtain that the forcing spectrum of a regular hexagonal system（a convex hexagonal system whose boundary of its inner dual graph is a regular hexagon）is continuous.In Chapter 5,We first obtain an exact formula for the maximum forcing number of a convex hexagonal system.Combining the expression for the maximum forcing number,we can conclude that the maximum anti-forcing number is either equal to twice the maximum forcing number,or twice minus 1.Specially,the anti-forcing spectrum of a convex hexagonal system is not necessarily continuous.By studying subsets of the anti-forcing spectrum,we find that the anti-forcing spectra of O（n,n,m）（n≥2 and m≥n is even）and O（n,m,m）（n≥2 is even and m≥n）lack the maximum anti-forcing number minus 1.Further,we give two kinds of convex hexagonal systems with continuous and non-continuous anti-forcing spectra:O（n₁,n₂,n₃）（n₁+n₂-n₃≤1）and O（2,n,n）（n≥2）.In Chapter 6,in order to study the mini-max theorem involved in anti-forcing prob-lems,we transformed the related problems of bipartite graphs into the cycle packing property of directed graphs,namely,the number of maximum arc-disjoint directed cy-cles is equal to the cardinality of the set of arcs intersecting all directed cycles.We find two types of directed graphs and some minors not satisfying the cycle packing property,and prove that they contain a minor isomorphic to O₁,M₅^*or M₅.