The minimum forcing number for the torus and hypercube
type: Item
instance of: scholarly article
title: The minimum forcing number for the torus and hypercube
zbMATH Open document ID: 0990.05101
DOI: 10.1016/S0012-365X(01)00228-X
author: Matthew E. Riddle
published in: Discrete Mathematics
publication date: 2002-05-15T00:00:00Z
review text: 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)].
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1741695
zbMATH Keywords: graph
zbMATH Keywords: perfect matching
zbMATH Keywords: forcing number
zbMATH Keywords: torus
zbMATH Keywords: hypercube
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1741695