On minimally one-factorable \(r\)-regular bipartite graphs
type: Item
instance of: scholarly article
title: On minimally one-factorable \(r\)-regular bipartite graphs
zbMATH Open document ID: 0952.05055
DOI: 10.1016/S0012-365X(99)00241-1
author: M. J. Funk
author: D. Labbate
published in: Discrete Mathematics
publication date: 2000-12-28T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1455605
zbMATH Keywords: regular bipartite graph
zbMATH Keywords: one-factor
zbMATH Keywords: one-factorization
zbMATH Keywords: Heawood graph
zbMATH Keywords: det-extremal graph
zbMATH Keywords: minimally one-factorable graph
reviewed by: Fedor V. Fomin
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00241-1
OpenAlex ID: W2069028059
description: scientific article; zbMATH DE number 1455605