PUB - Publikationen an der Universität Bielefeld

Let W-k be the number of walks of length k in a graph G, and put Delta(k) := Wk+1Wk-1-W-k(2). In recent work, it was shown that exactly one of the following four alternatives holds: Delta(1)greater than or equal to0 and Delta(k)=0 for all k=2,3,... in which case C is said to be harmonic, Delta(2k-10)>0 and Delta(2k)=0 for all k=1,2.... in which case G is said to be almost harmonic, Delta(2k-1)>0 for all k=1,2.... and Delta(2k)>0 for all sufficiently large k in which case G is said to be superharmonic, and Delta(2k-1)>0 for all k=1,2.... and Delta(2k)<0 for all sufficiently large k in which case G is said to be subharmonic. We examined all trees (up to isomorphism) with up to 18 vertices and determined how many of them belong to each of the four classes specified above. In agreement with a previously established result (cf. S. Grunewald, Harmonic Trees, Appl. Math. Lett., to appear) according to which a harmonic tree with at least 3 vertices always has exactly one vertex of degree a(2)-a+1 all of whose neighbours have degree a while all other vertices axe leaves (for some a &ISIN; N-&GE;2), exactly three (with 1, 2, and 7 vertices, respectively) of those trees turned out to be harmonic, no one is almost harmonic, 11 are superharmonic (of which the smallest has 12 vertices), and all others-some 99.994% of all trees examined-are subharmonic.