Maximizing the minimum and maximum forcing numbers of perfect matchings of graphs (Q6073878)

Let \(G\) be a simple graph with 2\(n\) vertices. 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\). \textit{Z. Che} and \textit{Z. Chen} [MATCH Commun. Math. Comput. Chem. 66, No. 1, 93--136 (2011; Zbl 1265.05001)] proposed the problem to characterize the graphs \(G\) with \(f(G) = n-1\) and later they showed that for a bipartite graph \(G\), \(f(G) = n-1\) if and only if \(G\) is \(K_{n,n}\). In this paper, the authors completely solve the problem of Che and Chen [loc. cit.], and show that \(f(G) = n -1\) if and only if \(G\) is a complete multipartite graph or a graph obtained from \(K_{n,n}\) by adding arbitrary edges in one partite set. For all graphs \(G\) with \(F(G) = n - 1\), they also prove that the forcing spectrum of each such graph \(G\) forms an integer interval by matching 2-switches and the minimum forcing numbers of all such graphs \(G\) form an integer interval from \(\lfloor n/2 \rfloor\) to \(n - 1\).