Handle bases and bounds on the number of subgraphs (Q1087883)

A handle basis for a finite strongly connected digraph G expresses G as an edge-disjoint union \(h_ 0,...,h_{d-1}\) of subgraphs such that \(h_ 0\) is a simple cycle, \(h_ 1,...,h_{d-1}\) are nontrivial simple paths, and each \(h_ i\), \(i>0\), meets the union of the previous h's at its endpoints. Here d means the cyclomatic number of G. It is shown that a subgraph of G is uniquely characterized by an integer valued function on the vertices (i.e., its boundary) and by the elements of a handle basis which it intersects. A subgraph H is said to be cyclically simple if, roughly speaking, no cycle has access to any other. The authors show that the number of such H with given boundary is at most \(2^{d-1}\). This generalizes a result of \textit{T. Foregger} [Proc. Am. Math. Soc. 49, 319-324 (1975; Zbl 0274.15007)] on the permanent of fully indecomposable nonnegative integer matrices. Finally the authors discuss a special case where the permanent is bounded by a Fibonacci number.