Qianqian Liu, Heping Zhang

Jun 17, 2021

Citations

0

Citations

Journal

Discret. Appl. Math.

Abstract

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.

Text copied to clipboard

copied to clipboard