A NOTE ON THE COMPLEXITY OF GRAPHS

Abstract. The number of splanning trees in a finite graph is first expressed as the derivative (at 1) of a determinant and then in terms of a zeta function. This generalizes a result of Hashimoto to non-regular graphs. Let G be a finite graph. The complexity of G, denoted κ, is the number of spanning trees in G. This quantity has long been known to be related to matrices associated with G (see [1]). When G is regular, Hashimoto [2] expressed κ as a limit involving the zeta function of the graph and asked if his expression still holds for irregular graphs. In this note, we show that the answer is yes. In particular, we derive a formula for the complexity as the derivative of a determinant involving the adjacency matrix of the graph and use this and a generalized version of Ihara’s theorem ([3,4]) to get the desired result. Let G be a graph with ν vertices and ε edges. Suppose we order the vertices: (x1,..., xν). The adjacency matrix A = (aij) is the matrix of zeros and ones such that aij = 1 if and only if xi and xj are adjacent. We let D = (dij) be the diagonal element with dii = di − 1 where di is the degree of the vertex xi. Finally, let Q = D − I. For a complex variable u, let f(u) = det(I − uA+ u2Q). Theorem. f ′(1) = 2( − ν)κ. Proof. Let Mu = I − uA+ u2Q and let Muk = (muk;ij) denote the matrix Mu with each entry of the kth row replaced by its corresponding derivative with respect to u. Then det(Mu) ′ = pi sgn(pi)(