Walk counting and Nikiforov’s problem

Abstract

For a given graph, let wk denote the number of its walks with k vertices and let λ1 denote the spectral radius of its adjacency matrix. Nikiforov asked in [Linear Algebra Appl 418 (2006), 257–268] whether it is true in a connected bipartite graph that λr1≥ws+rws for every even s≥2 and even r≥2? We construct here several infinite sequences of connected bipartite graphs with two main eigenvalues for which the ratio ws+rλr1ws is larger than~1 for every even s,r≥2, and thus provide a negative answer to the above problem.