On the Determinant of Kőnig–Egerváry Graphs
Kevin Pereyra · 2026
Read On the Determinant of Kőnig–Egerváry Graphs by Kevin Pereyra (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-25055.txt.
Introduction
Pereyra furthers the study of graph unimodularity through Kőnig-Egerváry graphs. He introduces a new factorization inside the Kőnig-Egerváry class. Partitioning vertices into perfect-flower and perfect-flower-free parts, he proves it factors into two determinants. The two factors belong to the two induced subgraphs. He obtains the analogous result for the permanent. The decomposition reduces it to two very different subgraphs. One ties to Sterboul-Deming patterns with perfect matching; the other follows critical independent sets.
Catalog record
| CREATOR | Kevin Pereyra |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36836 |
| LICENSE | http://creativecommons.org/publicdomain/zero/1.0/ |
| RIGHTS | CC0 |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.25055
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Determinant of Kőnig–Egerváry Graphs Kevin Pereyra 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 G , we consider the partition of V ( G ) V(G) into its perfect-flower part P F ( G ) PF(G) and its perfect-flower-free part P F F ( G ) PFF(G) , and prove that det ( G ) = det ( G [ P F ( G ) ] ) det ( G [ P F F ( G ) ] ) . \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 [ P F ( G ) ] G[PF(G)] , whose structure is closely related to Sterboul–Deming configurations with perfect matching, and the graph G [ P F F ( G ) ] 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. MSC 05C70, 05C75 1 Introduction Let \alpha(G) denote the cardinality of a maximum independent set, and let \mu(G) be the size of a maximum matching in G=(V,E) . It is known that \alpha(G)+\mu(G) equals the order of G , in which case G is a König–Egerváry graph [ 3 , 7 , 28 ] . Kőnig-Egerváry graphs have been extensively studied [ 2 , 9 , 17 , 18 , 10 ] . It is known that every bipartite graph is a König–Egerváry graph [ 6 ] . These graphs were independently introduced by Deming [ 3 ] , Sterboul [ 28 ] , and [ 7 ] . The term subgraph in here is understood as a subgraph defined by a graph and a given matching in that graph. In [ 5 ] , Edmonds introduced the following concepts relative to a matching M of a graph G and its subgraphs. An M -blossom of G is an odd cycle of length 2k+1 with k edges in M . The vertex not saturated by M in the cycle is called the base of the blossom. An M -stem is an M -alternating path of even length (possibly zero) connecting the base of the blossom with a vertex not saturated by M in G . The base is the only common vertex between the blossom and the stem. An M -flower is a blossom joined with a stem. The vertex not saturated by M in the stem is called the root of the flower. In [ 28 ] , Sterboul introduced the concept of a posy for the first time. An M -posy consists of two (not necessarily disjoint) M -blossoms joined by an M-alternating path that starts and ends with edges in M. The endpoints of the path are the bases of the two blossoms. There are no internal vertices of the path in the blossoms. Sterboul [ 28 ] was the first to characterize König–Egerváry graphs via forbidden configurations relative to a maximum matching. Subsequently, Korach, Nguyen, and Peis [ 15 ] reformulated this characterization in terms of simpler configurations, unifying the structures of flowers and posies. Later, Bonomo et al. [ 1 ] obtained a purely structural characterization based on forbidden subgraphs. More recently, in [ 11 , 13 , 14 ] , results were obtained that simplify working with flower and posy structures. Theorem 1.1 ( [ 28 ] ) . For a graph G , the following properties are equivalent: 1. G is a non-Kőnig-Egerváry graph. 2. For every maximum matching M , there exists an M -flower or an M -posy in G . 3. For some maximum matching M , there exists an M -flower or an M -posy in G . The set of vertices of G lying in a flower or posy, for any maximum matching, is denoted by SD(G) , and we write KE(G)=V(G)-SD(G) . The sets SD(G) and KE(G) constitute the SD–KE decomposition of the graph. A graph G is called a Sterboul–Deming graph if KE(G)=\emptyset . Essentially, it can be regarded as the structural counterpart of a Kőnig-Egerváry graph. Characterizations of Sterboul–Deming graphs can be found in [ 23 ] . The SD–KE decomposition admits a factorization for the determinant of the adjacency matrix of a graph [ 14 , 22 ] , that is, \det(G)=\det(G[KE(G)])\det(G[SD(G)]). We say that a graph is unimodular if the determinant of its adjacency matrix is \pm 1 . The above naturally reduces the problem of studying the unimodularity of graphs to studying the unimodularity of Kőnig-Egerváry or Sterboul-Deming graphs. Unimodular Sterboul-Deming graphs have been studied in [ 12 , 20 ] . Another graph decomposition that factorizes the determinant is the one known as the critical independence decomposition of Larson [ 16 ] , which partitions the graph into a Kőnig-Egerváry graph and a 2-bicritical graph [ 26 ] . In this work we advance the study of the unimodularity of Kőnig-Egerváry graphs via decompositions. Given a matching M of G , an M - perfect flower is a pair (C,P) with the following properties. The subgraph C is an odd cycle of length 2k+1 containing exactly k edges of M . The path P is a non-trivial M -alternating path, say P=p_{1},p_{2},\ldots,p_{t} , whose first and last edges belong to M . Moreover, V(C)\cap V(P)=\{p_{1}\}. Thus paths of length one are allowed in the definition of an M -perfect flower; in that case the unique edge of the path is both the first and the last edge, and hence it must belong to M . Paths of length zero are not allowed in this definition. We define the perfect-flower part of G as the set of vertices of G that belong to some M -perfect flower, for some matching M , and we denote it by PF(G) , that is PF(G):=\left\{\,v\in V(G):\begin{aligned} &v\text{ belongs to an }M\text{-perfect--flower}\\ &\text{for some maximum matching }M\end{aligned}\right\}. And define the perfect-flower-free part of G as PFF(G):=V(G)-PF(G). This decomposition was first defined in [ 21 ] in order to study the structure of critical independent sets in Kőnig-Egerváry graphs. In this work we prove that, for every Kőnig–Egerváry graph G , the perfect-flower decomposition of the vertex set is compatible with both the determinant and the permanent of the adjacency matrix. More precisely, if V(G)=PF(G)\cup PFF(G), then \det(G)=\det(G[PF(G)])\det(G[PFF(G)]) and \operatorname{perm}(G)=\operatorname{perm}(G[PF(G)])\operatorname{perm}(G[PFF(G)]). The determinant factorization is the one relevant to unimodularity. Indeed, within the class of Kőnig–Egerváry graphs, it reduces the problem of studying whether \det(G)=\pm 1 to the corresponding induced subgraphs G[PF(G)] and G[PFF(G)] . In particular,