Forcing Matching Number And Spectrum Of Graph P_2n×C_2m+1

The forcing number of a graph is the smallest cardinality of a matching edge set which can determine one perfect matching of the graph. This concept was originally introduced for Kekule structures of benzenoid systems by Harary et al. The same idea appeared in an earlier paper of Randic and Klein under the name "innate degree of freedom". This notion has arisen in the study of finding resonance structures of a given molecule in chemistry.Let M be a perfect matching of a graph G. A forcing set for a perfect matching M of G is a subset S of M,such that S is contained in no other perfect matching of G. The cardinality of a forcing set with the smallest size is called the forcing number of M,and is denoted by f(G;M). The minimum (resp. maximum) forcing number of G is the minimum (resp. maximum) value of forcing numbers of all perfect matchings of G, and is denoted by f(G) (resp. F(G)). The spectrum of the forcing numbers for a graph G is defined as:Spec(G)={k|there exists a perfect matching M of G such that f(G;M)=k}. Afshani et al. defined the matching 2-switch and obtained that the forcing spectrum of any column continuous grid is continuous.In this thesis, we mainly study the forcing number and forcing spectrum of the graph P2n×C2m+1.According to the characteristics of perfect matchings, In 2008 we proved that the minimum forcing number and the maximum forcing number of G are n-[n/3] and 2n. respectively. Furthermore, we constructed a perfect matching M such that f(P2n×C3;M)=r for any integer r∈[n-[n/3],2n]. Basing on this, here we discuss the forcing number and forcing spectrum of P2n×C2m+1 for any n and m. For the maximum forcing number of the graph P2n×C2m+1, Xiaoyan Jiang prove that:F(P2n×C2m+1)=n{m+1). For the minimum forcing number of the graph P2n×C2m+1,we obtain that the minimum forcing number of the graph P2n×C2m+1 by looking for independent matching alternating cycles for n=l,n=2 or m=2. For any n and m, we obtain a upper bound of the minimum matching forcing number. We prove that the forcing spectrums of the graphs P2 x C2m+1, P4×C2m+1 and P2n×C5 are continuous. For any n and m, we give a subset of forcing spectrum which is an integer interval.