Let $G$ be a simple graph with $2n$ vertices and a perfect matching. The forcing number $f(G,M)$ of a perfect matching $M$ of $G$ is the smallest cardinality of a subset of $M$ that is contained in no other perfect matching of $G$. Among all perfect matchings $M$ of $G$, the minimum and maximum values of $f(G,M)$ are called the minimum and maximum forcing numbers of $G$, denoted by $f(G)$ and $F(G)$, respectively. Then $f(G)leq F(G)leq n-1$. Che and Chen (2011) proposed an open problem: how to characterize the graphs $G$ with $f(G)=n-1$. Later they showed that for bipartite graphs $G$, $f(G)=n-1$ if and only if $G$ is complete bipartite graph $K_{n,n}$. In this paper, we solve the problem for general graphs and obtain that $f(G)=n-1$ if and only if $G$ is a complete multipartite graph or $K^+_{n,n}$ ($K_{n,n}$ with arbitrary additional edges in the same partite set). For a larger class of graphs $G$ with $F(G)=n-1$ we show that $G$ is $n$-connected and a brick (3-connected and bicritical graph) except for $K^+_{n,n}$. In particular, we prove that the forcing spectrum of each such graph $G$ is continued by matching 2-switches and the minimum forcing numbers of all such graphs $G$ form an integer interval from $lfloorfrac{n}{2}rfloor$ to $n-1$.
Download