
On the non-backtracking spectral radius of graphs
Author(s) -
Hongying Lin,
Bo Zhou
Publication year - 2022
Publication title -
the electronic journal of linear algebra
Language(s) - English
Resource type - Journals
eISSN - 1537-9582
pISSN - 1081-3810
DOI - 10.13001/ela.2022.6507
Subject(s) - spectral radius , backtracking , mathematics , combinatorics , adjacency matrix , radius , matrix (chemical analysis) , row , geometry , graph , discrete mathematics , physics , eigenvalues and eigenvectors , algorithm , computer science , chemistry , quantum mechanics , computer security , chromatography , database
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.