Edge Reconstruction of the Ihara Zeta Function

Gunther Cornelissen, Janne Kool


We show that if a graph $G$ has average degree $\overline d \geq 4$, then the Ihara zeta function of $G$ is edge-reconstructible. We prove some general spectral properties of the edge adjacency operator $T$: it is symmetric for an indefinite form and has a "large" semi-simple part (but it can fail to be semi-simple in general).  We prove that this implies that if $\overline d>4$, one can reconstruct the number of non-backtracking (closed or not) walks through a given edge, the Perron-Frobenius eigenvector of $T$ (modulo a natural symmetry), as well as the closed walks that pass through a given edge in both directions at least once.


Graph; Edge reconstruction conjecture; Ihara zeta function; Non-backtracking walks

Full Text: