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

Page view(s)

22
checked on Nov 8, 2024

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.