|Affiliations:||Mathematical Institute of the Serbian Academy of Sciences and Arts||Title:||Walk counting and Nikiforov’s problem||Journal:||Open Journal of Discrete Applied Mathematics||Volume:||3||Issue:||1||First page:||11||Last page:||19||Issue Date:||10-Feb-2020||Rank:||M53||DOI:||10.30538/psrp-odam2020.0024||URL:||https://pisrt.org/psrpress/j/odam/2020/1/3/walk-counting-and-nikiforov-s-problem.pdf||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.
|Keywords:||Walks in a graph | spectral radius | main eigenvalues||Publisher:||PSR Press||Project:||Graph theory and mathematical programming with applications in chemistry and computer science|
Show full item record
checked on Nov 28, 2022
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.