The minimum forcing number of graphs and involutory weighted adjacency matrices
In the authors' words
Let be a graph with a perfect matching. The minimum forcing number of is the smallest size of a matching in that is contained in exactly one perfect matching. For the -hypercube () Diwan (2019) determined by using a linear algebraic method, and Mohammadian (2022) generalized this method and showed that when a bipartite graph admits order and an involutory weighted adjacency matrix over a field , where denotes the Cartesian product. In this paper, we further prove that if , then for every , where is the -vertex path; this recovers Mohammadian's result when , and the lower bound is attained for . Moreover, we extend this method to non-bipartite graphs. Recursively constructing the adjacency matrix of the folded hypercube over the binary field , we prove that for every even . Combined with Mohammadian's result for odd , this establishes the same formula for all .
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 19 pages, 3 figures