On forcing matching number of boron–nitrogen fullerene graphs

Let GG be a graph that admits a perfect matching MM. A forcing set SS for a perfect matching MM is a subset of MM such that it is contained in no other perfect matchings of GG. The smallest cardinality of forcing sets of MM is called the forcing number   of MM. Computing the minimum forcing number of perfect matchings of a graph is an NP-complete problem. In this paper, we consider boron–nitrogen (BN) fullerene graphs, cubic 3-connected plane bipartite graphs with exactly six square faces and other hexagonal faces. We obtain the forcing spectrum of tubular BN-fullerene graphs with cyclic edge-connectivity 3. Then we show that all perfect matchings of any BN-fullerene graphs have the forcing number at least two. Furthermore, we mainly construct all seven BN-fullerene graphs with the minimum forcing number two.

► We obtain the matching forcing spectrum of some tubular BN-fullerene graphs. ► We show that all BN-fullerene graphs have the minimum forcing number at least two. ► We construct all seven BN-fullerene graphs with the minimum forcing number two.