A lower bound on the number of one-factors in bicubic graphs
| dc.contributor.author | Horton, J., D. | |
| dc.date.accessioned | 2023-03-01T18:28:03Z | |
| dc.date.available | 2023-03-01T18:28:03Z | |
| dc.date.issued | 1984 | |
| dc.description.abstract | The number of one-factors in a bicubic graph is shown to be more than polynomial in the number of vertices. Thus the permanent of a matrix of 0's and 1's in which each row and column includes precisely three 1's is more than polynomial. This improves the known lower bound of 3n. The form of the bound for a graph with 2n vertices is cnan [an superscript], where c is some constant and a < log 2[subscript] (9/4)=.85... . OTHER KEYWORDS: permanents, 0-1 matrices | |
| dc.description.copyright | Copyright @ J. D. Horton, 1984. | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/14810 | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | A lower bound on the number of one-factors in bicubic graphs | |
| dc.type | technical report |
Files
Original bundle
1 - 1 of 1