Det-Extremal Bipartite Graphs
Abstract
Let G be a balanced bipartite graph with a bipartite adjacency matrix A. We call G det-extremal if |det(A)|=per(A). If every edge of G belongs to a perfect matching, then G is matching covered. Det-extremal cubic bipartite graphs of connectivity 3 and 2 have been characterized by McCuaig and Funk et al., respectively. In this paper, we extend the above results by investigating the structure of det-extremal bipartite graphs. Due to the fact that only the edges belonging to perfect matchings contribute to the det-extremal property, we focus on det-extremal bipartite graphs that are matching covered. Firstly, we derive that a matching covered plane bipartite graph is det-extremal if and only if it has a plane bipartite ear decomposition such that each interior face is of size two modulo four. Then we turn to general matching covered bipartite graph, and we associate its bipartite ear decomposition with a standard perfect matching M*. By establishing the properties of its M*-alternating cycles, we provide the characterization of a general matching covered det-extremal bipartite graph in terms of standard bipartite ear decomposition.
Related
- When are random regular triangle-free graphs bipartite?
- Negative edge correlation in complete bipartite graphs
- A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs
- Exact three-component covers in 2-coloured random bipartite graphs
- Almost Gorenstein edge rings of bipartite graphs and their h-vectors
BibTeX
@article{li2026detextremal,
title = {{Det-Extremal Bipartite Graphs}},
author = {Wei Li},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
month = oct,
doi = {10.37236/14353},
url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p20},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Det-Extremal Bipartite Graphs
AU - Wei Li
PY - 2026
DA - 2026/10/23
JO - The Electronic Journal of Combinatorics
DO - 10.37236/14353
UR - https://www.combinatorics.org/ojs/index.php/eljc/article/view/v33i4p20
AB - Let G be a balanced bipartite graph with a bipartite adjacency matrix A. We call G det-extremal if |det(A)|=per(A). If every edge of G belongs to a perfect matching, then G is matching covered. Det-extremal cubic bipartite graphs of connectivity 3 and 2 have been characterized by McCuaig and Funk et al., respectively. In this paper, we extend the above results by investigating the structure of det-extremal bipartite graphs. Due to the fact that only the edges belonging to perfect matchings contribute to the det-extremal property, we focus on det-extremal bipartite graphs that are matching covered. Firstly, we derive that a matching covered plane bipartite graph is det-extremal if and only if it has a plane bipartite ear decomposition such that each interior face is of size two modulo four. Then we turn to general matching covered bipartite graph, and we associate its bipartite ear decomposition with a standard perfect matching M^*. By establishing the properties of its M^*-alternating cycles, we provide the characterization of a general matching covered det-extremal bipartite graph in terms of standard bipartite ear decomposition.
SN - 1077-8926
ER -