Relations Between Forcing Sets, Anti-forcing Sets,and Alternating Sets Of Plane Graphs

Let G be a graph. A perfect matching of G is a set of independent edges covering all vertices of G. Let M be a perfect matching of G and S ? E(G). If S ? M and S is not contained by other perfect matchings of G, then S is called a forcing set of M; If S ? E(G)\M and G- S has a single perfect matching M, then S is called an anti-forcing set of M. The forcing number(resp. anti-forcing number) of M, denoted by f(G, M)(resp. af(G, M)), is the smallest cardinality over all forcing sets(resp.anti-forcing sets) of M. The maximum forcing number(resp. maximum anti-forcing number) of G is the maximum value of forcing numbers(resp. anti-forcing numbers)of all perfect matchings of G, denoted by F(G)(resp. Af(G)).A cycle of G is called an M-alternating cycle if its edges appear alternately between M and E(G)\M. Two M-alternating cycles are compatible if either they are disjoint or they intersect only at edges in M. For a plane bipartite graph G, Pachter et al. showed that f(G, M) is equal to the maximum number of disjoint M-alternating cycles in G; Lei et al. showed that af(G, M) is equal to the maximum number of compatible M-alternating cycles in G.Let G be a plane graph and R a set of inner faces of G. R is called an alternating set of G if G has a perfect matching such that the boundaries of all faces in R are M-alternating. Further, an alternating set R is called a resonant set if the faces in R are mutually disjoint. The cardinality of a maximum resonant set of G is called the resonant number of G, denoted by res(G). Pachter’s result implies F(G) ≥ res(G).A hexagonal system H is a 2-connected finite plane graph such that every inner face is bounded by a regular hexagon of side length one. Usually, a maximum resonant set of H is also a Clar set, and its size is the Clar number of H, denoted by Cl(H). Zheng et al. showed that the graph obtained from H by deleting any maximum resonant set has a unique perfect matching. Salem et al. showed that the graph obtained from H by deleting any maximal alternating set has a unique perfect matching. Combining the results above, Xu et al. showed that H has a perfect matching M with f(H, M) = F(H) such that f(H, M) equals the maximum number of disjoint M-alternating hexagons in H, the maximum forcing number of H equals its Clar number, and proposed a conjecture that the maximum forcing number of any polyomino graph can be computed in polynomial time. A polyomino graph is a finite connected subgraph in the infinite plane square grid in which every inner face is bounded by a square and every edge belongs to at least one square.A maximum alternating set of a hexagonal system H is also a Fries set, and its size is the Fries number of H, denoted by F ries(H). Clearly, Af(H) ≥ F ries(H).Lei et al. obtained a fact that H has a perfect matching M with af(H, M) = Af(H)such that af(H, M) equals the number of M-alternating hexagons in H, and further showed that the maximum anti-forcing number of H equals its Fries number.Motivated by the works above, we further study the relations between matching forcing numbers, matching anti-forcing numbers, and the number of alternating facial cycles in hexagonal systems or polyomino graphs.This thesis consists of five chapters. In chapter 1, we introduce some useful concepts, terminologies and notations. Then we introduce the background of resonant sets and matching forcing numbers, and summarize their developments. In the end of this chapter, the main results of this thesis are listed.In chapter 2, we study the properties of maximum resonant sets and maximal alternating sets in a polyomino graph H, and give the relation between the maximum forcing number of H and its resonant number. Specifically, we show that the graph obtained from H by deleting any maximum resonant set has a unique perfect matching, the graph obtained from H by deleting any maximal alternating set has a unique perfect matching, the maximum forcing number of H equals its resonant number, and further confirms a conjecture proposed by Xu et al.In chapter 3, we study the relations between the maximum forcing number and the number of alternating hexagons in a hexagonal system H. By improving Zheng’s approach, we prove that for every perfect matching M of H with the maximum forcing number, i.e. f(H, M) = F(H), the maximum number of disjoint M-alternating hexagons in H is equal to f(H, M); From Cl(H) = F(H), H has a Clar set consisting of M-alternating hexagons. We further prove that for any two members of the set consisting of F(H) disjoint M-alternating cycles in H their interiors are disjoint, and for every member C of the set, the subgraph of H formed by C together with its interior is a linear hexagonal chain.In chapter 4, we study the relations between matching forcing numbers and the number of alternating squares in a polyomino graph H. We prove that for every perfect matching M of H with the maximum or second maximum forcing number,i.e. f(H, M) = F(H) or F(H)- 1, the maximum number of disjoint M-alternating squares in H is equal to f(H, M). In the case where f(H, M) = F(H), we prove that for any two members of the set consisting of f(H, M) disjoint M-alternating cycles in H their interiors are disjoint, and for every member C of the set, the subgraph of H formed by C together with its interior is a zigzag chain.In chapter 5, we study the relations between matching anti-forcing numbers and the number of alternating hexagons in a hexagonal system H. We prove that for every perfect matching M of H with the maximum or second maximum anti-forcing number, i.e. af(H, M) = Af(H) or Af(H)-1, the number of M-alternating hexagons in H equals af(H, M), any two members of af(H, M) non-crossing compatible M-alternating cycles in H have disjoint interiors, and for every member C of these cycles, the subgraph of H formed by C together with its interior is a linear hexagonal chain. In the end of this chapter, we study the hexagonal systems H without nice Triphenylene and prove that every perfect matching M′of H is always equal to the number of all M′-alternating hexagons in H if and only if H contains no Triphenylene as its nice subgraph.