Anti-forcing Number Of Some Classes Of Lattice Graphs

Let G be a finite simple connected graph,E(G)and V(G)are edge set and vertex set of G.An independent edge set M is a perfect matching for G if and only if all the points in V(G)are M-saturated.The anti-forcing number of M is the minimum number of edges of G whose deletion results in a subgraph with a unique perfect matching M.The anti-forcing spectrum of G is the set of all anti-forcing numbers of its perfect matchings.Accordingly,t,he largest and smallest integers in the anti-forcing spectrum are called the largest and smallest anti-forcing numbers of G,denot,ed by F(G)and f(G),respectively.Ladder graph Ln is the Descartes Product of path Pn and P2.In the first chapter,we briefly introduce the research background and achievements of ladder graph,give some basic concepts and important lemmas.In Chapter 2,we give a decomposition theorem,which divides Ln into two segments.A perfect matching anti-compulsion number of Ln is the sum of the anti-compulsion numbers of each segment corresponding to some perfect matching.By using the decomposition Theorem,we obtain the anti-forcing spectra of Ln and the continuity of the spectra.By counting all the perfect matching of Ln classifications by the anti-forcing number or the horizontal matching edge number,two combinatorial interpretations about the Fibonacci number are obtained.In the second chapter,firstly,by means of Ln deformation of ladder graph,we get edge-deleted ladder graph ILn-i and L-shaped ladder graph LLn-i,then calculate the anti-forcing spectra of edge-deleted of ladder graphs and L-shaped ladder graphs.In the process,a combinatorial interpretation of Fibonacci number is obtained.In Chapter 4,the anti-forcing numbers of the deformed Ladder Graph TLn1,n2,n3 and XLn1,n2,n3,n4 are calculated by using the previous conclusions.