Authors: | Feng, Lihua Lu, Lu Stevanović, Dragan |
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
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.