On the Determinant of Kőnig-Egerváry Graphs

Abstract

Several graph decompositions that factorize the determinant of the adjacency matrix isolate a Kőnig-Egerváry part, such as the SD--KE decomposition and the critical independence decomposition of Larson. This suggests that the study of graph unimodularity can be approached, to a large extent, through the structure of Kőnig-Egerváry graphs. In this paper we advance this point of view by introducing a new determinant factorization inside the class of Kőnig-Egerváry graphs. More precisely, given a Kőnig-Egerváry graph $G$, we consider the partition of $V(G)$ into its perfect-flower part $PF(G)$ and its perfect-flower-free part $PFF(G)$, and prove that \[ \det(G)=\det(G[PF(G)])\det(G[PFF(G)]). \] We also obtain the analogous factorization for the permanent. This decomposition provides a new tool for the study of unimodularity, reducing the problem to two induced subgraphs of a very different nature: the graph $G[PF(G)]$, whose structure is closely related to Sterboul--Deming configurations with perfect matching, and the graph $G[PFF(G)]$, which is governed by the theory of critical independent sets. In this way, the paper gives a new structural framework for the study of unimodular graphs through Kőnig-Egerváry theory.