On the determinant of Kőnig–egerváry graphs
Utilitas Mathematica · 10.05.2026 · 127 · 217-237
DOI: 10.61091/um127-15 ↗Kurz gefasst
Fachartikel in der Zeitschrift Utilitas Mathematica, online erschienen am 10.05.2026. Verfasst von Kevin Pereyra.
Abstract (Originalsprache)
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 within 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 very different nature: the graph \(G[PF(G)]\), whose structure is closely related to Sterboul–Deming configurations with perfect matchings, and the graph \(G[PFF(G)]\), which is governed by the theory of critical independent sets. In this way, the paper provides a new structural framework for the study of unimodular graphs through Kőnig–Egerváry theory.
Zitieren
APA
Pereyra, K. (2026). On the determinant of Kőnig–egerváry graphs. Utilitas Mathematica, 127, 217-237. https://doi.org/10.61091/um127-15
Vancouver
Pereyra K. On the determinant of Kőnig–egerváry graphs. Utilitas Mathematica. 2026;127:217-237. doi:10.61091/um127-15
BibTeX
@article{Pereyra2026,
author = {Pereyra, Kevin},
title = {On the determinant of Kőnig–egerváry graphs},
journal = {Utilitas Mathematica},
year = {2026},
volume = {127},
pages = {217--237},
doi = {10.61091/um127-15}
}
EUVIMED