# Generating functions of non-backtracking walks on weighted digraphs : Radius of convergence and Ihara's theorem

Loading...

##### Access rights

openAccess

##### Journal Title

##### Journal ISSN

##### Volume Title

A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

This publication is imported from Aalto University research portal.

View publication in the Research portal

View/Open full text file from the Research portal

Other link related to publication

View publication in the Research portal

View/Open full text file from the Research portal

Other link related to publication

##### Date

2024-10-15

##### Major/Subject

##### Mcode

##### Degree programme

##### Language

en

##### Pages

35

##### Series

Linear Algebra and Its Applications, Volume 699, pp. 72-106

##### Abstract

It is known that the generating function associated with the enumeration of non-backtracking walks on finite graphs is a rational matrix-valued function of the parameter; such function is also closely related to graph-theoretical results such as Ihara's theorem and the zeta function on graphs. In Grindrod et al. [13], the radius of convergence of the generating function was studied for simple (i.e., undirected, unweighted and with no loops) graphs, and shown to depend on the number of cycles in the graph. In this paper, we use technologies from the theory of polynomial and rational matrices to greatly extend these results by studying the radius of convergence of the corresponding generating function for general, possibly directed and/or weighted, graphs. We give an analogous characterization of the radius of convergence for directed (unweighted or weighted) graphs, showing that it depends on the number of cycles in the undirectization of the graph. We also consider backtrack-downweighted walks on unweighted digraphs, and we prove a version of Ihara's theorem in that case. Finally, for weighted directed graphs, we provide for the first time an exact formula for the radius of convergence, improving a previous result that exhibited a lower bound, and we also prove a version of Ihara's theorem.##### Description

Publisher Copyright: © 2024 The Author(s)

##### Keywords

Directed graph, Ihara's theorem, Non-backtracking walk, Rational function, Undirected part, Undirectization, Weighted graph

##### Other note

##### Citation

Noferini, V & Quintana, M C 2024, ' Generating functions of non-backtracking walks on weighted digraphs : Radius of convergence and Ihara's theorem ', Linear Algebra and Its Applications, vol. 699, pp. 72-106 . https://doi.org/10.1016/j.laa.2024.06.022