EUVIMEDEUVIMED entdecken
Crossref

On the determinant of Kőnig–egerváry graphs

Kevin Pereyra

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →