Utilizza questo identificativo per citare o creare un link a questo documento:
|Titolo:||On minimally one-factorable r-regular bipartite graphs|
|Autori interni:||FUNK, Martin|
|Data di pubblicazione:||2000|
|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.|
|Appare nelle tipologie:||1.1 Articolo su Rivista|
File in questo prodotto:
Non ci sono file associati a questo prodotto.
- PubMed Central loading...
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.