1,721,012 research outputs found
On Determinants and Permanents of Minimally 1-Factorable Cubic Bipartite Graphs
Full text linkA minimally 1-factorable cubic bigraph is a graph in which every 1-factor lies in precisely one 1-factorization. The author investigates determinants and permanents of such graphs and, in particular, proves that the determinant of any minimally 1-factorable cubic bigraph of girth 4 is 0
Characterizing Minimally 1-factorable r-Regular Bipartite Graphs
No full textAbstractThe possibilities for circuits of length 4 to appear together in a cubic bigraph are classified. That has consequences on the structure of minimally 1-factorable regular bigraphs, i.e. those in which each 1-factor lies in precisely one 1-factorization. We characterize minimally 1-factorable cubic bigraphs of girth 4
2-factors of regular graphs: a survey
No full textA 2–factor of a graph G is a 2–regular spanning subgraph of G. We survey
results on the structure of 2–factors in regular graphs obtained in the last
years by several authors
On minimally one-factorable r-regular bipartite graphs
No full textBy 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
- …
