Asymptotic results regarding the number of walks in a graph (Q1431948): Difference between revisions

Let \(W_k\) denote the number of walks of length \(k\) (\(\geq 0\)) in a finite graph \(G\), and define \(\Delta_k(G)=W_{k+1}W_{k-1}-W_k^2\). The authors consider the (asymptotic) behaviour of \(\Delta_k\) and show that exactly one of the following alternatives holds for a finite graph \(G\): (H) \(\Delta_1(G)\geq 0\) and \(\Delta_k(G)=0\) for all \(k\in\mathbb N_{\geq 2}\), in this case \(G\) is called harmonic. (H\(_0\)) \(\Delta_{2k-1}(G)>0\) and \(\Delta_{2k}(G)=0\) for all \(k\in\mathbb N\), in this case \(G\) is called almost harmonic. (H\(_+\)) \(\Delta_{2k-1}(G)>0\) for all and \(\Delta_{2k}(G)>0\) for all sufficiently large \(k\in\mathbb N\), in this case \(G\) is called superharmonic. (H\(_-\)) \(\Delta_{2k-1}(G)>0\) for all and \(\Delta_{2k}(G)<0\) for all sufficiently large \(k\in\mathbb N\), in this case \(G\) is called subharmonic. While the authors give examples of harmonic, superharmonic and subharmonic graphs, the question of existence of almost harmonic graphs is left open.