Det-Extremal Bipartite Graphs

Source abstract

Let $G$ be a balanced bipartite graph with a bipartite adjacency matrix $A$. We call $G$ det-extremal if $|\det(A)|=\text{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.