Global Forcing Numbers And Complete Forcing Numbers Of Some Graphs

Let G be a simple connected graph with edge set E(G) that admits a perfect matching. A global forcing set of G is any subset S of E(G) such that no two perfect matchings of G coincide on S. The number of edges in a global forcing set of the smallest cardinality is called the global forcing number of G. Similarly, a complete forcing set of G is a subset of E(G) on which the restriction of any perfect matching is a forcing set of the perfect matching. The minimum size of complete forcing sets of G is called the complete forcing number of G. In this article, we consider global forcing numbers or complete forcing numbers of some kinds of graphs. This paper is divided to three parts. We mainly introduce the background and research status of global forcing numbers and complete forcing numbers of graphs in the first part. In the second part, by constructive proof, explicit formulae for global forcing numbers of handgun-shaped benzenoid systems are given. In the third part, we study complete forcing numbers of primitive coronids at first. Then we give explicit formulae for complete forcing numbers of all-even-cycle chains. At last, by recursive decomposition, formulae for complete forcing numbers of catacondensed polyomino graphs and corresponding decomposition algorithm as well as its computational complexity is also given.