Study On The Forcing Matching Number And Spectra Of Some Classes Of Graphs

The minimum forcing number of a graph is the smallest cardinality of a matching which can determine uniquely 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 Klein and Randic under the name "innate degree of freedom". This concept originates from the study of resonance theory of molecular graph in chemistry.Let G be a graph with perfect matchings. 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 matchings of G. The smallest cardinality of forcing sets of M is called the forcing number of M, 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, denoted by f(G) (resp. F(G)). The forcing spectrum of G is defined as: Spec(G)={f(G, M)|M is a perfect matching of G}. Zhang et al. proved that the minimum forcing numbers of fullerene graphs are at least 3. and there are two classes of tubular graphs arriving in the lower bound. S. Kleinerman once showed that the maximum forcing number of C2m x C2n is mn.n by deleting a vertex subset. Afshani et al. obtained that the forcing spectrum of any column continuous grid is continuous.In this thesis, we mainly study the matching forcing number and forcing spectrum of some classes of graphs. We obtain the forcing spectrum of boron-nitrogen fullerene graphs with cyclic edge-connectivity 3, determine all boron-nitrogen fullerene graphs with cyclic edge-connectivity 4 whose minimum forcing number arrive in the lower bound 2, give the maximum forcing number of three classes of graphs, prove that the forcing spectrum of any even polygonal chain is continuous, investigate the continuity of forcing spectrum of two classes of cata-condensed hexagonal system.There are five chapters in the thesis. In Chapter one, we first introduce some basic concepts and notations. Then we mainly introduce the background of forcing number of graphs and present the research problems and their developments. At last, we outline the main results obtained in the following chapters.In Chapter two, we mainly study the forcing number of boron-nitrogen fullerene graphs. For the cyclic-edge connectivity 3, it is a class of tubular graphs Tn. We obtain that the forcing spectrum of Tn is an integer interval(?)by constructing a perfect matching M such that f(Tn,M)=k for any integer (?). Moreover, we characterize all seven boron-nitrogen fullerene graphs with minimum forcing number 2 and cyclic-edge connectivity 4.In Chapter three, we solve the maximum forcing number problem of some special classes of graphs by deleting an independent set of graphs:The maximum forcing number of non-bipartite graph C2n+i x Pim is m(n+1), and the maximum forcing numbers of toroidal 4-8 lattice T(p, q, t) and Klein-bottle 4-8 lattice K(p, q, t) both equal the number pq of all squares which cover all vertices of them.In Chapter four, we apply the connection of Z-transformation graphs to solve the continuity of forcing spectrum. First we prove that for any polyomino, the forc-ing spectrum is continuous, which generalizes the result of Afshani et al. about the continuous forcing spectrum of column continuous subgrid and simplifies their proof. Furthermore, we prove that the forcing spectrum of any even polygonal chain is con-tinuous by matching switch. In addition, we obtain the extremal values on the forcing numbers among all even polygonal chains with the given number of kinks.Continuing to apply Z-transformation graph, in Chapter five, we discuss two classes of cata-condensed hexagonal systems, and obtain that the forcing spectra of them are either continuous, or any two elements of forcing spectrum are not consec-utive, or there is only one gap in the spectrum.