PUB - Publikationen an der Universität Bielefeld

The aim of this note is to call attention to a simple regularity regarding the number of walks in a finite graph G. Let W-k denote the number of walks of length k(greater than or equal to 0) in G. Then W-a+b(2) less than or equal to W2aW2b holds for all a, b is an element of N-o while equality holds exclusively either (I) for all a, b is an element of N-o (in case G is a regular graph), or (II) for all a, b is an element of N, or (III) for all a, b is an element of N-o of equal parity (provided G is connected, this holds if and only if G is nonregular, yet semiregular graph), or (IV) for all a, b is an element of N of equal parity, or (V) just for a = b only. We show that all of these five cases can actually occur and discuss the resulting classification graphs in exactly five classes. (C) 2003 Elsevier Science Ltd. AN rights reserved.