Walks and the spectral radius of graphs

Given a graph G, write μ(G) for the largest eigenvalue of its adjacency matrix, ω(G) for its clique number, and wk(G) for the number of its k-walks. We prove that the inequalitiesfrac(wq + r (G), wq (G)) ≤ μr (G) ≤ frac(ω (G) - 1, ω (G)) wr (G)hold for all r \u3e 0 and odd q \u3e 0. We also generalize a number of other bounds on μ(G) and characterize semiregular and pseudo-regular graphs in spectral terms. © 2006 Elsevier Inc. All rights reserved