Let G be a simple graph with 2n vertices and a perfect matching. We denote by f(G) and F (G) the minimum and maximum forcing number of G, respectively. Hetyei obtained that the maximum number of edges of graphs G with a unique perfect matching is n. We know that G has a unique perfect matching if and only if f(G) = 0. Along this line, we generalize the classical result to all graphs G with f(G) = k for 0 ≤ k ≤ n − 1, and characterize corresponding extremal graphs as well. Hence we get a non-trivial lower bound of f(G) in terms of the order and size. For bipartite graphs, we gain corresponding stronger results. Further, we obtain a new upper bound of F (G). For bipartite graphs G, Che and Chen (2013) obtained that f(G) = n − 1 if and only if G is complete bipartite graph Kn,n. We completely characterize all bipartite graphs G with f(G) = n− 2.

This paper presents a new upper bound on the forcing number of graphs, f(G), and demonstrates its importance for bipartite graphs.

Some tight bounds on the minimum and maximum forcing numbers of graphs

Key Takeaway: This paper presents a new upper bound on the forcing number of graphs, f(G), and demonstrates its importance for bipartite graphs.