z-logo
open-access-imgOpen Access
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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here