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.