Projects per year
Abstract
It is known that the generating function associated with the enumeration of nonbacktracking walks on finite graphs is a rational matrixvalued function of the parameter; such function is also closely related to graphtheoretical 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 backtrackdownweighted 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.
Original language  English 

Pages (fromto)  72106 
Number of pages  35 
Journal  Linear Algebra and Its Applications 
Volume  699 
DOIs  
Publication status  Published  15 Oct 2024 
MoE publication type  A1 Journal articlerefereed 
Keywords
 Directed graph
 Ihara's theorem
 Nonbacktracking walk
 Rational function
 Undirected part
 Undirectization
 Weighted graph
Fingerprint
Dive into the research topics of 'Generating functions of nonbacktracking walks on weighted digraphs : Radius of convergence and Ihara's theorem'. Together they form a unique fingerprint.Projects
 1 Finished

Noferini_Vanni_AoF_Project: Noferini Vanni Academy Project
Noferini, V. (Principal investigator), Quintana Ponce, M. (Project Member), Barbarino, G. (Project Member), Wood, R. (Project Member) & Nyman, L. (Project Member)
01/09/2020 → 31/08/2024
Project: Academy of Finland: Other research funding