On minimally one-factorable \(r\)-regular bipartite graphs (Q1567270)

The famous Hall marriage theorem implies that every one-factor of an \(r\)-regular bipartite graph can be completed to a one-factorization, i.e. to a factorization of \(r\) one-factors. The authors study two classes of \(r\)-regular bipartite graphs. The first class is the class of minimally one-factorable graphs, i.e. graphs in which every one-factor belongs to precisely one one-factorization. It is proved that the Heawood graph is an instance of a minimally one-factorable graph. Also they show that minimally one-factorable \(r\)-regular bipartite graphs exist only for \(r\leq 3\). The authors construct a wide class \(\mathcal E\) of examples of minimally one-factorable cubic bipartite graphs containing the Heawood graph. The second class of graphs, the det-extremal graphs, is the class of bipartite graphs \(G\) with \(\det(G)=\text{per}(G)\). (\(\det(G)\) is the determinant and \(\text{per}(G)\) is the permanent of the adjacency matrix of \(G\).) In general \(\det(G)\leq \text{per}(G)\) and it is well known that \(\text{per}(G)\) equals the number of one-factors of \(G\). Using a numeric evaluation by computer the authors prove that the Heawood graph is the only cubic det-extremal graph with less than 26 vertices. Finally they show that disregarding the Heawood graph, the class \(\mathcal E\) contains a second instance of a det-extremal graph.