Walks and the spectral radius of graphs (Q852649)

The author provides lower and upper bounds on the spectral radius of a graph \(G\) in terms of walks and characterizes pseudo-regular and semiregular graphs in terms of their eigenvectors. Given a graph \(G\), with vertex set \(\{1,2, \dots, n\}\), a \(k\)-walk is a sequence of vertices \(v_1, \dots, v_k\) of \(G\) such that \(v_i\) is adjacent to \(v_{i+1}\) for all \(i=1,2, \dots, k-1\); \(w_k(G)\) denotes the number of \(k\)-walks in \(G\) and \(w(G)\) its clique number. The eigenvalues of the adjacency matrix \(A(G)\) of \(G\) are ordered as \(\mu(G)=\mu_1 \geq \cdots \geq \mu_n\). For every graph \(G\), the author shows that \[ \mu^r(G) \geq \frac{w_{q+r}(G)}{w_q(G)} \] for all \(r>0\) and odd \(q>0\). If equality holds, then each component of \(G\) is pseudo-regular or semiregular. For the case of even \(q\) he also obtains lower and upper bounds on \(\mu^r(G)\), \(r>0\). The main result for upper bounds on \(\mu(G)\) establishs that for every graph \(G\) and \(r \geq 1\) \[ \mu^r(G) \leq \frac{w(G)-1}{w(G)}w_r(G). \]