The minimum forcing number for the torus and hypercube (Q1348133)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The minimum forcing number for the torus and hypercube |
scientific article |
Statements
The minimum forcing number for the torus and hypercube (English)
0 references
15 May 2002
0 references
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)].
0 references
graph
0 references
perfect matching
0 references
forcing number
0 references
torus
0 references
hypercube
0 references