Minimum forcing numbers of perfect matchings of circular and prismatic graphs

Abstract

Let $G$ be a graph with a perfect matching. Denote by $f(G)$ the minimum size of a matching in $G$ that is uniquely extendable to a perfect matching in $G$. Diwan (2019) used linear algebra to prove that for the $d$-hypercube $Q_d$ ($d\ge 2)$, $f(Q_d)=2^{d-2}$, thus settling a conjecture of Pachter and Kim (1998). Recently, Mohammadian generalized this method to prove a general result: for a bipartite graph $G$ on $n$ vertices, if $G$ admits an involutory weighted adjacency matrix $A$ over a field $F$, then $f(G\square K_2)=\frac{n}{2}$, where $\square$ denotes the Cartesian product of two graphs. In this paper we obtain $f(G\square C_{2k})=n$ when a bipartite graph $G$ on $n$ vertices admits an involutory weighted adjacency matrix $A$ over a field $F$ of characteristic not 2, for all integers $k\ge 2$. Moreover, we demonstrate that this method can also be applied to some nonbalanced bipartite graphs $G$ when graphs $G$ admit a weighted bi-adjacency matrix with orthogonal rows.

18 pages, 4 figures