Research On Forcing Problems Of Perfect Matchings Of Graphs

A perfect matching of a graph is called a Kekule structure in organic chemistry.In 1985 Randic and Klein introduced the concept of "innate degree of freedom" for a Kekule structure when studying the resonance structure of organic molecules.Afterwards,it was called the forcing number by Harary,Klein and Zivkovic.Let G be a graph and M be a perfect matching of G.A subset S of M is called a forcing set of M if S is not contained in other perfect matching of G.The smallest cardinality of a forcing set of M is called the forcing number of M,denoted by f(G,M).The minimum and maximum forcing numbers of G is the minimum and maximum values of f(G,M)over all perfect matchings M of G,denoted by f(G)and F(G),respectively.The forcing spectrum of G is the set of forcing numbers of all perfect matchings of G.Afshani,Hatami and Mahmoodian proved that determining the minimum forcing number is NP-complete for bipartite graphs with the maximum degree 4.We assume that G has order 2n and a perfect matching.Since any n-1 edges of a perfect matching form a forcing set of it,we have 0≤f(G)≤F(G)≤n-1.Che and Chen proposed a problem:how to characterize the graphs G with f(G)= n-1.For bipartite graphs,they obtained that f(G)=n-1 if and only if G is complete bipartite graph Kn,n.In this thesis,we completely solve this open problem,and study some forcing properties of graphs with the maximum forcing numbers n-1 and n-2:minimum forcing number,forcing spectrum and the set of minimum forcing numbers.We obtain some upper and lower bounds of the maximum and minimum forcing numbers for general graphs.By studying resonance graphs of toroidal grids,we verify that forcing spectra of non-bipartite toroidal grids are an integer interval.This thesis contains six chapters.In Chapter 1,we first introduce some basic concepts,terminologies and notations.And then we introduce the background and development of forcing problems of perfect matchings.In the end,we summarize main results of this thesis.In Chapter 2,we solve the problem of Che and Chen and obtain that f(G)= n-1 if and only if G is a complete multipartite graph with each partite set having size no more than n or a graph in Kn,n+(a family of graphs obtained by adding arbitrary additional edges in one partite set to complete bipartite graph Kn,n).For a graph G with F(G)=n-1,we show that G is n-connected,and 1-extendable except for graphs in Kn,n+.For all such 1-extendable graphs,we also determine which of them are not 2-extendable.Besides,we obtain that f(G)≥[n/2],and all minimum forcing numbers of such graphs form an integer interval[[n/2],n-1].Further,we prove that any two perfect matchings of G can be obtained by applying repeatedly matching 2-switches.Thus the forcing spectrum of each such graph is an integer interval.In Chapter 3,we characterize all bipartite graphs with the minimum forcing number n-2.For all bipartite graphs G with F(G)=n-2,we prove that any two perfect matchings of G can be obtained from each other by repeatedly applying matching 2-or 3-switches.Especially,if G is C6-free(containing no induced subgraphs isomorphic to a cycle of length 6),then it is enough to apply matching 2-switches.Thus forcing spectra of C6-free graphs are an integer interval.Moreover,we obtain that f(G)≥[n/2]-1,and all minimum forcing numbers of such graphs form an integer interval[[n/2]-1,n-2].In Chapter 4,we consider the upper bound of the number of edges for graphs G with f(G)=k for 0 ≤k≤n-1.Conversely,we get a lower bound of f(G).For bipartite graphs,we gain corresponding stronger results.Such lower bounds enable one to compute the minimum forcing numbers of some graphs.Similarly,by considering the lower bound of the number of edges for graphs G with F(G)=k for 0 ≤k≤n-1,we obtain a new upper bound of F(G).In following two chapters,we study the forcing spectrum of toroidal grid T(n,m,r)which is obtained from an n x m chessboard Pn+1 × Pm+1 by first sticking the left and right sides together,then identifying the top and bottom sides with a torsion r squares with 1 ≤r ≤m.Obviously,T(n,,m,m)is isomorphic to Cn×Cm.In chapters 5 and 6,we consider the resonance graphs of C2n+1×C2m and T(2n+1,2m,2r)using different methods and apply results to forcing spectra.For 1≤r≤m,we show that the resonance graph of T(2n+1,2m,2r)is disconnected and consists of exactly two isomorphic components.Thus the forcing spectrum of T(2n+1,2m,2r)is an integer interval.Besides,we obtain the maximum forcing numbers of toroidal grids:If m/(r,m)is even then F[T(2n+1,2m,2r))=m(2n+1)/2,otherwise F(T(2n+1,2m,2r))=m(2n+1)+(r,m)/2,where(r,m)represents the maximum common factor of r and m.