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.
2000
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11563/419
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 8
social impact