Complete forcing numbers of the Rook’s graphs

A subset of the edges of a perfect matching in a graph is called a forcing set for it if no other perfect matching contains that subset. A complete forcing set of a graph is a subset of the edges such that the intersection of every perfect matching with the subset forms a forcing set for that perfect matching. The minimum size of the complete forcing sets of a graph is called the complete forcing number of the graph. In this paper, we determine the complete forcing number of the Cartesian product of two complete graphs, also known as Rook’s graphs, and present a minimum-sized complete forcing set for these graphs. For higher-dimensional Cartesian products of complete graphs, we use the result of the 2-fold Cartesian product case to present upper and lower bounds for the complete forcing number.