2025/02/16 by Qiaoyun Shi, Heping Zhang, Shi, Qiaoyun +1
Computer Science · Mathematics · #05C70 05C50 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2502.10981
openalex publication_date 2025/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Qd (d≥ 2), f(Qd)=2d-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\Box K2)=(n)/(2), where \square denotes the Cartesian product of two graphs. In this paper we obtain f(G\Box C2k)=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≥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.