A graph theoretic upper bound on the permanent of a nonnegative integer matrix. I

Let A be a fully indecomposable n×n matrix with nonnegative integer entries. Then the permanent of A is bounded above by 1+min{Π(c_i?1), Π(r_i?1)}, where c_i and r_i are the column and row sums of A. The inequality results from a bound on the number of disjoint cycle unions in an associated multigraph. This bound can improve via contractions.