By extension from Hall's famous marriage theorem, every one-factor of an r-regular bipartite graph extends to a factorisation of r one-factors. Such a graph G is minimally one-factorable if every one-factor belongs to precisely one one-factorisation. We show that if G is minimally one-factorable then r is at most 3. It is a well-known fact that the permanent of the adjacency matrix of G, per(G), is the number of one-factors of G. If the determinant of the adjacency matrix is det(G), a curious fact is that the Heawood graph H has been shown (by computer search) to be the only cubic bipartite graph with less than 26 vertices for which det(G) = per(G). Such graphs are said to be det-extremal. In addition, H is minimally one-factorable. A class of minimally one-factorable cubic graphs which contains a second instance of a det-extremal example after H is constructed in this paper.
On minimally one-factorable r-regular bipartite graphs
FUNK, Martin;LABBATE, Domenico
2000-01-01
Abstract
By extension from Hall's famous marriage theorem, every one-factor of an r-regular bipartite graph extends to a factorisation of r one-factors. Such a graph G is minimally one-factorable if every one-factor belongs to precisely one one-factorisation. We show that if G is minimally one-factorable then r is at most 3. It is a well-known fact that the permanent of the adjacency matrix of G, per(G), is the number of one-factors of G. If the determinant of the adjacency matrix is det(G), a curious fact is that the Heawood graph H has been shown (by computer search) to be the only cubic bipartite graph with less than 26 vertices for which det(G) = per(G). Such graphs are said to be det-extremal. In addition, H is minimally one-factorable. A class of minimally one-factorable cubic graphs which contains a second instance of a det-extremal example after H is constructed in this paper.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
