The minimum forcing number for the torus and hypercube (Q1348133)

The forcing number of a perfect matching \(M\) in a graph is the smallest size of a subset \(S\) of \(M\) that is in no other perfect matching. Let \(C_{2n}\) and \(C_{2m}\) be cycles of length \(2n\) and \(2m\), respectively; then their Cartesian product is called a \(2n\times 2m\) torus. The author proves that the minimum forcing number on such a torus with \(m\geq n\) is \(2n\), and on an \(n\)-dimensional hypercube it is \(2^n/4\) if \(n\) is even. These results resolve conjectures of \textit{L. Pachter} and \textit{P. Kim} [Discrete Math. 190, No. 1-3, 287-294 (1998; Zbl 0956.05087)].