On the non-backtracking spectral radius of graphs

Abstract

Given a graph $G$ with $m\ge 1$ edges, the non-backtracking spectral radius of $G$ is the spectral radius of its non-backtracking matrix $B(G)$ defined as the $2m \times 2m$ matrix where each edge $uv$ is represented by two rows and two columns, one per orientation: $(u, v)$ and $(v, u)$, and the entry of $B(G)$ in row $(u, v)$ and column $(x,y)$ is given by $\delta_{vx}(1-\delta_{uy})$, with $\delta_{ij}$ being the Kronecker delta. A tight upper bound is given for the non-backtracking spectral radius in terms of the spectral radius of the adjacency matrix and minimum degree, and those connected graphs that maximize the non-backtracking spectral radius are determined if the connectivity (edge connectivity, bipartiteness, respectively) is given.