Matching Forcing Numbers Of Bipartite Graphs

Let G be a graph that admits a perfect matching. 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 cardinality of a forcing set of M 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, denoted by f(G) (resp. F(G)), is the minimum (resp. maximum) value of forcing numbers of all perfecting matchings of G. The spectrum of forcing numbers of G is the set of forcing numbers of all perfect matchings. P. Admas et al. showed that the minimum forcing set is N P-complete for bipartite graphs with maximum degree 3.Perfect matching is corresponding to Kekule structure in chemistry, and the matching forcing number is also called the degree of freedom of Kekule structure. The idea of "forcing " appears in many research fields in both graph theory and combinatorics, such as graph coloring, geodetic set, Latin square and block design. Recently, the matching forcing number has been extensively studied , and new concepts, such as global forcing number, anti-Kekule number, anti-forcing number and forcing hexagon, have been proposed.In this thesis, we mainly study matching forcing numbers of bipartite graphs.By Hall Theorem, M.E. Riddle obtained a lower bound for f(G). In chapter two, we improve the lower bound of Riddle by determining canonical ordering of vertices. We also obtain a necessary condition for the forcing number of a graph equal to a given natural number k , as well as sufficient and necessary conditions for f(G) equal to the minimum number of trailing vertices of all canonical orderings of color set B.The molecular graph of toroidal fullerene (also toroidal polyhex) is a finite trivalent bipartite graph embedded on torus with only hexagonal faces. It can be determined by a string of three integers p,q,t (p≥1,q≥1,0≤t≤p - 1) and denoted by H(p,q,t). In chapter three, by trailing-vertex-method, we obtain that f(H(p, q, t))≥min{p, q}, and equality holds for p≤q, or p > q and t∈{0,p - q,p - q + 1,…,p- 1}. In general, we show that f(H(p, q, t)) is equal to the side length of a maximum triangle on H(p, q, t). Basing on this result, we provide a linear algorithm to compute f(H(p, q, t)).In chapter four, we generalize the result of Riddle about C_2m×C_2n to S(p,q,t) (p>>>>> 1, q≥1, 0≤t≤p - 1), where S(p, q, t) is the 4-regular bipartite quadragulation of the torus defined similarly as H(p,q,t). In this chapter, we show if p≤q, f(S(p,q,t)) = 2p; if p > q and 0≤t < q, or p > q and p - q + 1≤t≤p-1, f(S(p, q, t)) = 2q; if p > q , q≤t≤p - q, f(S(p, q, t)) is equal to the half circumstance of the minimum character rectangle in S(p, q, t) plus 1.A bipartite Klein bottle polyhex can also be obtained from a p×q-parallelogram of a hexagonal lattice with usual identifications of sides and can be determined by two parametersp and q, and is denoted simply by K(p,q). In chapter five, we show if p≤q, then f(K(p, q)) = p; else if q < p≤2q, then f(K(p, q)) = q; else p > 2q, thenBoron-Nitrogen Fullerenes are cubic plane bipartite graphs with only square and hexagonalfaces. In chapter six, we study the relationship between the maximum forcing number F(G), the face independent numberα^*(G), the resonance number r(G), and the maximum perfect Clar structure H of a Boron-Nitrogen Fullerene G, and show that F(G) =α^*(G) = r(G) =|H|. By trailing-vertex-method, the forcing numbers of B₁₂N₁₂, B₁₆N₁₆,B₂₂N₂₂, B₂₇N₂₇ and B₂₈N₂₈ are obtained. We also obtain the upper bounds for minimum forcing numbers, the maximum forcing numbers of three classes of capped BN-nanotubes.In chapter seven, we give a construction for the forcing set of a perfect matching of P_m×P-n and obtain the spectrum of forcing numbers of P_m×C_2n which settles an open problem of P. Afshani et al.