A lower bound on the number of one-factors in bicubic graphs
Loading...
Files
Date
1984
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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