Graph-Counting Polynomials for Oriented Graphs

If F is a set of subgraphs F of a finite graph E we define a graph-counting polynomial pF(z) = Sigma(F is an element of F)z(vertical bar F vertical bar) In the present note we consider oriented graphs and discuss some cases where F consists of unbranched subgraphs E. We find several situations where something can be said about the location of the zeros of p(F). Let F be a set of subgraphs F of a finite graph E. We denote by vertical bar F vertical bar the number of edges of F and define a polynomial p(F)(z) = Sigma(F is an element of F) z(vertical bar F vertical bar) (graph-counting polynomial associated with F). The case of unoriented graphs has been discussed earlier (see [4-6] and [1-3]); here we mostly consider oriented graphs. We shall find that for suitable F we can restrict the location of the zeros of p(F) (for instance to the imaginary axis). The proofs will be based on the following fact: Lemma (Asano-Ruelle). Let K-1, K-2 be closed subsets of the complex plane C such that K-1, K-2 (sic) 0 and assume that A + Bz(1) + Cz(2) + Dz(1)z(2) not equal 0 when z(1) is not an element of K-1, z(2) is not an element of K-2 Then A + Dz not equal 0 when z is not an element of - K1K2 where - K1K2 is minus the set of products of an element of K-1 and an element of K-2. (The replacement of A + Bz(1) + Cz(2) + Dz(1)z(2) by A + Dz is called Asano contraction and denoted (z(1), z(2)) -> z). For a proof see for instance the Appendix A of [6]. The results given below follow rather directly from this lemma.