Let \(\mathcal{F}\) be a set of subgraphs F of a finite graph E. We denote by |F| the number of edges of F and define a polynomial

$$\begin{aligned} p_\mathcal{F}(z)=\sum _{F\in \mathcal{F}}z^{|F|} \end{aligned}$$

(graph-counting polynomial associated with \(\mathcal{F}\)). The case of unoriented graphs has been discussed earlier (see [4,5,6] and [1,2,3]); here we mostly consider oriented graphs.

We shall find that for suitable \(\mathcal{F}\) we can restrict the location of the zeros of \(p_\mathcal{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 \(\mathbf{C}\) such that \(K_1,K_2\not \ni 0\) and assume that

$$\begin{aligned} A+Bz_1+Cz_2+Dz_1z_2\ne 0\qquad \mathrm{when}\qquad z_1\notin K_1,z_2\notin K_2 \end{aligned}$$

Then

$$\begin{aligned} A+Dz\ne 0\qquad \mathrm{when}\qquad z\notin -K_1K_2 \end{aligned}$$

where \(-K_1K_2\) 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_1z_2\) by \(A+Dz\) is called Asano contraction and denoted \((z_1,z_2)\rightarrow z\)).

For a proof see for instance the Appendix A of [6]. The results given below follow rather directly from this lemma.

1 Definitions: Subgraphs of an Oriented Graph

We say that a pair (V, E) of finite sets is an oriented graph if \(V\ne \emptyset \) and we are given two maps \(x',x'':E\rightarrow V\) such that \(x'(e)\ne x''(e)\) for all \(e\in E\). The elements x of V are vertices, and the elements e of E are oriented edges with endpoints \(x'(e),x''(e)\); e is outgoing at \(x'(e)\) and ingoing at \(x''(e)\) and we write \(e: x'(e)\rightarrow x''(e)\). We allow different edges \(e_1,e_2\) such that \(e_1:x'\rightarrow x''\) and \(e_2:x'\rightarrow x''\) or \(e_2:x''\rightarrow x'\).

We say that (V, E) is bipartite if we are given a partition of V into nonempty sets \(V_1\) and \(V_2\) such that for each \(e\in E\) the points \(x'(e)\) and \(x''(e)\) are in different sets of the partition \(\{V_1,V_2\}\).

We call a subset F of E a subgraph of (V, E). We say that F is connected if for each partition \(\{F_1,F_2\}\) of F there is an \(x\in V\) which is an endpoint of both some \(e_1\in F_1\) and some \(e_2\in F_2\). A subgraph is thus a union of connected components \(F_j\) in a unique way.

We say that F is an unbranched subgraph if, for each \(x\in V\),

$$\begin{aligned} |\{e\in F:x'(e)=x\}|\le 1\qquad \mathrm{and}\qquad |\{e\in F:x''(e)=x\}|\le 1 \end{aligned}$$

We say that an unbranched subgraph is a loop subgraph if for each \(x\in V\) we have

$$\begin{aligned} |\{e\in F:x'(e)=x\}|=|\{e\in F:x''(e)=x\}| \end{aligned}$$

We denote by U(E), resp. L(E), the set of unbranched subgraphs, resp. loop subgraphs of the oriented graph (V, E). If F is an unbranched subgraph, we can write F as a disjoint union of connected components \(F_j\) which are either loops (i.e., \(F_i\in L(E)\)) or, if they are not loops, have different endpoints \(x'_j\) and \(x''_j\) such that \(x'_j\rightarrow \cdots (e)\cdots \rightarrow x''_j\) for each \(e\in F_j\).

Introduce now complex variables \(z'_e,z''_e\), write \(Z'=(z'_e)_{e\in E}\), \(Z''=(z''_e)_{e\in E}\) and, for each \(x\in V\), let

$$\begin{aligned} p_x(Z',Z'')=\left( a'(x)+\sum _{e:x'(e)=x}z'_e\right) \left( a''(x)+\sum _{e:x''(e)=x}z''_e\right) \end{aligned}$$
(1)

with some choice of the \(a'(x),a''(x)\in \mathbf{C}\). For small \(\epsilon >0\) we also write

$$\begin{aligned} p_x^\epsilon (Z',Z'') =\left( a'(x)+\sum _{e:x'(e)=x}(z'_e+\epsilon )\right) \left( a''(x)+\sum _{e:x''(e)=x}(z''_e+\epsilon )\right) \end{aligned}$$

and

$$\begin{aligned} \tilde{p}_x=1+p_x,\quad \tilde{p}_x^\epsilon =1+p_x^\epsilon \end{aligned}$$

Choosing between \(p_x\) and \(\tilde{p}_x\) for each x and applying Asano contractions \((z'_e,z''_e)\rightarrow z_e\) for all \(e\in E\) to the polynomials

$$\begin{aligned} \prod _{x\in V}(p_x(Z',Z'')\hbox { or }\tilde{p}_x(Z',Z'')),\quad \prod _{x\in V}(p_x^\epsilon (Z',Z'')\hbox { or }\tilde{p}_x^\epsilon (Z',Z'')) \end{aligned}$$
(2)

we obtain polynomials

$$\begin{aligned} P(Z),\quad P^\epsilon (Z) \end{aligned}$$

where \(Z=(z_e)_{e\in E}\) and

$$\begin{aligned} \lim _{\epsilon \rightarrow 0}P^\epsilon (Z)=P(Z) \end{aligned}$$

We shall obtain examples of \(p(z)=p_\mathcal{F}(z)\) by taking all components \(z_e\) of Z equal to z.

2 Unbranched Subgraphs of an Oriented Graph

If there are only \(p_x\) factors in (2) and we assume \(a'(x)a''(x)=1\) for all x, we have

$$\begin{aligned} P(Z)=\sum _{F\in U(E)}\prod _{F_j\subset F}^\mathrm{conn} [a''(x'_j)a'(x''_j)]_{F_j\mathrm{not}\,\mathrm{loop}}\prod _{e\in F_j}z_e \end{aligned}$$
(3)

where the product is over the connected components \(F_j\) of F and \(x'_j\), \(x''_j\) are the endpoints of \(F_j\) if j is not a loop; \([a''(x'_j)a'(x''_j)]\) is replaced by 1 if \(F_j\) is a loop.

If we take \(a'(x)=a''(x)=1\) and set all \(z_e\) equal to z we obtain the unbranched subgraph counting polynomial

$$\begin{aligned} p_\mathrm{unbranched}(z)=\sum _{F\in U(E)}z^{|F|} \end{aligned}$$
(4)

Proposition 2.1

The zeros of the unbranched subgraph counting polynomial (4) are all real and strictly negative.

To prove this let \(\alpha ', \alpha ''\in (-\pi /2,\pi /2)\). Assuming

$$\begin{aligned} \mathrm{Re}(z'_e+\epsilon )e^{-i\alpha '}>0\qquad ,\qquad \mathrm{Re}(z''_e+\epsilon )e^{-i\alpha ''}>0 \end{aligned}$$

for all \(e\in E\) and all \(\epsilon >0\), we have \(\prod _{x\in V}p_x^\epsilon (Z',Z'')\ne 0\) and therefore by the Asano-Ruelle Lemma \(P^\epsilon (Z)\ne 0\) if \(e^{-i(\alpha '+\alpha '')}z_e\) is in a neighborhood of the positive real axis and \(-\pi<\alpha '+\alpha ''<\pi \). Let p(z) and \(p^\epsilon (z)\) be obtained by taking all \(z_e\) equal to z in P(Z) and \(P^\epsilon (Z)\). Then \(p^\epsilon (z)\ne 0\) if \(\arg z\in (-\pi ,\pi )\). Using Hurwitz’s theorem we let \(\epsilon \rightarrow 0\) in \(p^\epsilon (z)\) and find that either p(z) vanishes identically or \(p(z)\ne 0\) if \(\arg z\in (-\pi ,\pi )\). Clearly \(p(0)\ne 0\) because \(\emptyset \subset U(E)\) and we obtain thus \(p_\mathrm{unbranched}(z)=p(z)\ne 0\) if z is not real strictly negative. \(\square \)

[In fact since \(a'(x)=a''(x)=1\) we could have done without \(\epsilon \) in the present situation].

Let now deg\(_2\) be the max over \(x\in V\) of the number \(d'_x\) of outgoing edges at x times the max over x of the number \(d''_x\) of ingoing edges at x. Then \(p_x(Z',Z'')\ne 0\) if \(|z'_e|<1/d'_x\) and \(|z''_e|<1/d''_x\) for all \(e\in E\), so that \(P(Z)\ne 0\) if all \(z_e<1/\mathrm{deg}_2\). Finally \(p(z)\ne 0\) if \(|z|<1/\mathrm{deg}_2\), i.e., the zeros of p(z) are negative and bounded above by \(-1/\mathrm{deg}_2\).

Remark 2.2

Given \(V_0\subset V\) let \(a'(x)=a''(x)=1\) if \(x\in V_0\) and \(a'(x)=a''(x)=0\) if \(x\notin V_0\). The polynomial p counts then unbranched polynomials going through all \(x\notin V_0\). The proof of the Proposition 2.1 still applies (but now \(\epsilon \) is indeed needed) and one finds that the zeros of p are real less then or equal zero if p does not vanish identically.

The following result is relevant to Sect. 3.2 below.

Proposition 2.3

Let (V, E) be bipartite corresponding to a partition \(\{V_1,V_2\}\) of V and let \(U_\mathrm{even}(E)\) consist of the unbranched subgraphs F such that \(|F_j|\) is even for each connected component \(F_j\) of F. We define

$$\begin{aligned} p_\mathrm{unbranched\,even}(z)=\sum _{F\in U_\mathrm{even}(E)}z^{|F|} \end{aligned}$$
(5)

Assume that the odd connected subgraphs in U(E) come in pairs \((G,\bar{G})\) connecting the same vertices and both G, \(\bar{G}\) are loops or not loops. If \(x',x''\) (resp. \(\bar{x}',\bar{x}''\)) are the endpoints of non-loop G (resp. \(\bar{G}\)) we also assume \(x'=\bar{x}''\), \(x''=\bar{x}'\). Under these conditions the zeros of the polynomial (5) are all purely imaginary.

To prove this let us in Eq. (1) take \(a'(x)=(1+i)/\sqrt{2}\) if \(x\in V_1\), \(a'(x)=(1-i)/\sqrt{2}\) if \(x\in V_2\) and let \(a''(x)\) be the complex conjugate \(a'(x)^*\) of \(a'(x)\) in all cases. We use thus the \(p_x(Z',Z'')\), \(p_x^\epsilon (Z',Z'')\) corresponding to those \(a'(x)\), \(a''(x)\).

We obtain polynomials P(Z), resp. \(P^\epsilon (Z)\), by Asano contractions of \(\prod p_x(Z',Z'')\), resp. \(\prod p_x^\epsilon (Z',Z'')\), and (3) gives

$$\begin{aligned} P(Z)=\sum _{F\in U(E)}\prod _{F_j\subset F}^\mathrm{conn}\gamma (F_j)\prod _{e\in F_j}z_e \end{aligned}$$
(6)

with \(\gamma (F_j)=a''(x'_j)a'(x''_j)\) if \(F_j\) is not a loop, and \(\gamma (F_j)=1\) if \(F_j\) is a loop. If \(|F_j|\) is even, \(x'_j\) and \(x''_j\) are both in either \(V_1\) or \(V_2\), so that \(\gamma (F_j)=1\). If \(|F_j|\) is odd, \(x'_j\) and \(x''_j\) are in different sets of the partition \((V_1,V_2)\), so that \(a''(x'_j)a'(x''_j)=((1\pm i)/\sqrt{2})^2\) and \(\gamma (F_j)=\pm i\). Choose now a pair \((G,\bar{G})\) with odd \(|G|=|\bar{G}|\) then \(\gamma (G)+\gamma (\bar{G})=0\) so that the terms in p(z) corresponding to F containing a connected component G or \(\bar{G}\) cancel. This holds for all pairs \((G,\bar{G})\) with odd \(|G|=|\bar{G}|\) and therefore

$$\begin{aligned} p(z)=\sum _{F\in U(E)}\prod _{F_j\subset F}^\mathrm{conn}\gamma (F_j)z^{|F_j|} =\sum _{F\in U_\mathrm{even}(E)}z^{|F|}=p_\mathrm{unbranched\,even}(z) \end{aligned}$$

With our choice of \(a',a''\) we see that if \(\alpha ',\alpha ''\in (-\pi /4,\pi /4)\) and

$$\begin{aligned} \mathrm{Re}(z'_e+\epsilon )e^{-i\alpha '}>0\qquad ,\qquad \mathrm{Re}(z''_e+\epsilon )e^{-i\alpha ''}>0 \end{aligned}$$

for all \(e\in E\), we have \(\prod _{x\in V}p_x^\epsilon (Z',Z'')\ne 0\). Therefore by the Asano-Ruelle Lemma \(P^\epsilon (Z)\ne 0\) if

$$\begin{aligned} -\pi /2<\alpha '+\alpha ''<\pi /2\qquad \mathrm{and}\qquad (\forall e\in E)\,\,\,(z_e+\epsilon ')e^{-i(\alpha '+\alpha '')}>0 \end{aligned}$$

for some \(\epsilon '>0\). We take all \(z_e\) equal to z and use Hurwitz’s theorem to let \(\epsilon \rightarrow 0\). Since \(\emptyset \in U_\mathrm{even}\), p does not vanish identically and we obtain \(p(z)\ne 0\) if Re\((z)>0\), or by symmetry if Re\((z)\ne 0\). \(\square \)

3 Oriented Subgraphs of a Non-oriented Graph

Let \((V,E_0)\) be a non-oriented graph. There are different ways to associate an oriented graph with (V, E). Here we define the oriented graph \((V,\tilde{E}_0)\) where each non-oriented edge \(e\in E_0\) with endpoints \(x_1,x_2\in V\) is replaced by two oriented edges \(e',e''\in \tilde{E}_0\) such that \(x'(e')=x_1,\,x''(e')=x_2\) and \(x'(e'')=x_2,\,x''(e'')=x_1\). We have thus \(|\tilde{E}_0|=2|E_0|\). The subgraphs \(\tilde{F}\) of \((V,\tilde{E}_0)\), i.e., the subsets of \(\tilde{E}_0\) may be called oriented subgraphs of \((V,E_0)\).

3.1 Unbranched Subgraphs of a Non-oriented Graph

From Proposition 2.1 we know that the polynomial counting oriented unbranched subgraphs of \((V,E_0)\), i.e.,

$$\begin{aligned} p_\mathrm{oriented\,unbranched} (z)=\sum _{\tilde{F}\in U(\tilde{E}_0)}z^{|\tilde{F}|} =\sum _{\tilde{F}\in U(\tilde{E}_0)}\prod _{\tilde{F}_j\subset \tilde{F}}^\mathrm{conn}z^{|\tilde{F}_j|} \end{aligned}$$

has all its zeros real strictly negative. Note that without orientation

$$\begin{aligned} p_\mathrm{unbranched} (z)=\sum _{F\in U(E_0)}z^{|F|} =\sum _{F\in U(E_0)}\prod _{F_j\subset F}^\mathrm{conn}z^{|F_j|} \end{aligned}$$

and it is known (see [5]) that this has all its zeros with real part strictly negative. [The set \(U(E_0)\) of unbranched subgraphs of \(E_0\) and the connected components of a non-oriented F are defined in the obvious manner].

Let us now assume that \((V,E_0)\) has only simple edges between vertices. It is interesting to compare the connected components \(F_j\) of some non-oriented unbranched subgraph F with the possible corresponding oriented connected components \(\tilde{F}_{j\alpha }\) of an unbranched oriented subgraph \(\tilde{F}\) such that, for each edge e of F, one or both of the corresponding edges \(e',e''\) belongs to \(\tilde{F}\). If \(|F_j|=1\) then \(F_j=e\) for some non-oriented \(e\in E_0\) with endpoints \(x_1,x_2\) and there are two oriented edges \(e',e''\in \tilde{E}_0\) corresponding to e. Then, corresponding to \(F_j\) there are three possible connected components \(\tilde{F}_{j\alpha }\subset \tilde{E}_0\), namely \(\{e'\},\{e''\},\{e',e''\}\), and \(|\tilde{F}_{j\alpha }|\) is 1 or 2. If \(|F_j|>1\), there correspond to \(F_j\) two oriented \(\tilde{F}_{j\alpha }\). We obtain thus for \(\tilde{E}_0\) the polynomial

$$\begin{aligned} p_\mathrm{oriented\,unbranched} (z) =\sum _{F\in U(E_0)}\prod _{F_j:|F_j|=1}^\mathrm{conn}(2z+z^2)\prod _{F_j:|F_j|>1}^\mathrm{conn}(2z^{|F_j|}) \end{aligned}$$

3.2 Even Oriented Unbranched Subgraphs of a Non-oriented Graph

For a bipartite graph \(E_0\) we obtain pairs \((G,\bar{G})\) of subgraphs of \(\tilde{E}_0\) as in Proposition 2.3 by orientation reversal so that

$$\begin{aligned} p_\mathrm{oriented\,unbranched\,even} (z)=\sum _{\tilde{F}\in U_\mathrm{even}(\tilde{E}_0)}z^{|\tilde{F}|} \end{aligned}$$

has all its zeros purely imaginary by Proposition 2.3.

Let \((V,E_0)\) have only simple edges between vertices. We define

$$\begin{aligned} U'(E_0)=\{F:~\mathrm{for~all~connected~components}~F_j~\mathrm{of}~F~\mathrm{either} ~|F_j|=1~\mathrm{or}~|F_j|~\mathrm{is even}\} \end{aligned}$$

Then we have

$$\begin{aligned} p_\mathrm{oriented\,unbranched\,even} (z)=\sum _{F\in U'(E_0)}z^{2|\{|j:|F_j|=1\}|}.\prod _{j:|F_j|>1}(2z)^{|F_j|} \end{aligned}$$

for the unbranched even subgraph counting polynomial of \(\tilde{E}_0\).