2017/12/10 by Diwan, Ajit A. · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1712.03535
Let M be a perfect matching in a graph. A subset S of M is said to be a forcing set of M, if M is the only perfect matching in the graph that contains S. The minimum size of a forcing set of M is called the forcing number of M. Pachter and Kim [Discrete Math. 190 (1998) 287--294] conjectured that the forcing number of every perfect matching in the n-dimensional hypercube is at least 2n-2, for all n ≥ 2. Riddle [Discrete Math. 245 (2002) 283-292] proved this for even n. We show that the conjecture holds for all n ≥ 2. The proof is based on simple linear algebra.