Walk counting and Nikiforov’s problem

For a given graph, let w k 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 λ r 1 ≥ w s + r w s 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 w s + r λ r 1 w s is larger than~1 for every even s , r ≥ 2 , and thus provide a negative answer to the above problem.