Complete Forcing Numbers Of Grid Graphs On Torus

In 1985,Randic and Klein proposed the innate degree of freedom of a Kekule structure when they studied the resonance structure of molecules.Harary et al.called it the forcing numbers of a perfect matching of a graph.To a perfect matching M of a graph G,a subset of M is a forcing set if the intersection of it and M is not contained in other perfect matchings of the graph G.In 2015,Xu et al.proposed the concept of complete forcing sets of graphs.A edge subset S of G is called a complete forcing set of G if the intersection of each perfect matching M of G and S is a forcing set of M.The complete forcing numbers of G is the cardinality of a minimum complete forcing set of G.By the equivalent condition for complete forcing numbers of graphs,we know that a complete forcing set of a graph is both the strengthening of the global forcing set and the unification of the forcing set and anti-forcing set of perfect matchings.The main purpose of studying the complete forcing number of a graph is to find methods for computing the complete forcing number and explore the relationship between the complete forcing number and other invariants.By proposing elementary edge cut decomposition,He and Zhang showed that the complete forcing number for a connected graph is bounded above by 2 times the cyclomatic number,and obtained the formulas for the complete numbers of cylinderal grids Pm□Cn.This thesis aims to develop the method to compute the complete forcing numbers of grid graphs on torus Cm□Cn.In this thesis,we give a reachable upper and lower bounds for complete forcing number of grid graphs on torus under general conditions,and the exact value under mostly conditions.Firstly,this thesis proposes the elementary set decomposition by promoting the elementary edge cut decomposition and gives an upper bound and a lower bound for complete forcing numbers of grid graphs on torus.Then this thesis uses elementary set decomposition to give the formulas for the complete forcing numbers of grid graphs on torus Cm□Cn where m,n≥3,one of m and n is odd,anohter is even and where m,n are even,one of m and n is equal or greater than 14,anohter is equal or greater than 24,they are equal to the lower bound.Finally,this thesis uses reduction to absurdity to prove that the complete forcing numbers of grid graphs on torus C4 □ Cn is mn+4 where n≥4 and n is even by cases analysis,it attains the upper bound.