PUB - Publikationen an der Universität Bielefeld

Let W-k denote the number of walks of length k(greater than or equal to 0) in a finite graph G, and define Delta(k) = Deltak(G) := Wk+1 Wk-1 - Wk. The condition A(2k-1) (G) > 0 is satisfied for all k is an element of N, and for all graphs G except the harmonic graphs for which Delta(k) = 0 holds for all k > 2-and thus, in particular, for the regular graphs for which Delta(k) = 0 holds for all k is an element of N. In contrast, the sign Of Delta(2k)(G) may be positive as well as negative, depending on k and G. We show that, for every finite graph G, there exist unique numbers N is an element of N-0, tau(1),...,tau(N), a(1),...,a(N), b(1),...,b(N) is an element of R-greater than or equal to0 with 0 less than or equal to tau(1) < tau(2) < ... < tau(N) and a(1) + b(1), a(2) + b(2),...,a(N) + b(N) > 0 that can be computed in terms of the main eigenvalues and -angles of G such that Delta(k) = Sigma(nu-1)(N)(a(nu) +(-1)(k-1) b(nu)) t(nu)(k-1) holds for all k in N. Consequently, the limits lim(k-->infinity) (2k)rootDelta(2k+1) and lim(k-->infinity) (2k-1)rootDelta(2k) always exist and the sign Of Delta(2k) is constant for all sufficiently large k. (C) 2003 Elsevier Science Ltd. All rights reserved.