Towards a structural characterization of unimodular graphs with a unique perfect matching

Abstract

We study determinantal properties of graphs with a unique perfect matching. A recent determinantal decomposition (Jaume-Panelo-Martinez, 2025) expresses any such graph as the union of a Konig-Egerváry ˝ subgraph and a non-KE subgraph, yielding a factorization of the adjacency determinant. While the KE part is always unimodular, we focus here on the non-KE component. We introduce a broad family of non-KE graphs and characterize exactly when they are unimodular. Our approach is combinatorial, based on Sachs subgraphs, alternating paths and barbell decompositions, and sheds new light on the structure of unimodular graphs with a unique perfect matching.