WorksMathematics
The real eigenvalues of the non-backtracking Laplacian
Abstract
Let be a simple graph on nodes and edges, with minimum degree at least . We prove that the non-backtracking Laplacian of has at least real eigenvalues, counted with algebraic multiplicity, where is the number of connected components of and is the number of bipartite ones. More precisely, at least of them lie in and at least lie in . We show that the bound is sharp, and that a connected -regular graph attains it if and only if it is strictly Ramanujan, i.e., every adjacency eigenvalue satisfies . For completeness, we also show that the non-backtracking Laplacian has at most real eigenvalues.
Introduction
While most of the spectral theory of simple graphs concerns symmetric matrices, such as the adjacency matrix and the graph Laplacians (we refer to [10, 8, 18] for three monographs), a growing body of work is devoted to non-symmetric operators, and in particular to non-backtracking operators. The eigenvalues of these operators are in general complex, and even a basic question such as how many of them are real is often difficult to answer.
Non-backtracking operators first appeared in 1989 in the work of Hashimoto [16], in the context of zeta functions of graphs, and they have since proved useful in many areas, including algebraic graph theory [30, 4, 11], the study of Ramanujan graphings [3], epidemic spreading [29, 9], community detection [20, 7, 6], and centrality measures [22, 31]. We refer to [32, 12, 13, 28, 1, 2, 15, 23, 5] for further results on non-backtracking operators and their applications.
The idea behind these operators is to study walks on a graph that are never allowed to return along the edge they have just traversed. More precisely, let be a simple graph on nodes and edges, with minimum degree at least . Each edge of admits two orientations, and we write for the oriented edge with input and output . Its inverse is . This gives oriented edges, which we label as in such a way that
A non-backtracking random walk on is a discrete-time Markov process on the oriented edges such that the probability of going from to is
In particular, the assumption that has minimum degree at least guarantees that the denominator is always positive. Moreover, one can also see a non-backtracking random walk as a process on , but in this case the probability that the walker moves from a vertex to one of its neighbors depends on the vertex she came from. Hence, this process is not Markovian on .
Non-backtracking random walks are encoded by the non-backtracking graph or Hashimoto graph of , denoted , which is the directed graph whose vertices are the oriented edges of , and which has a directed edge from to if and only if
i.e., if and only if a non-backtracking random walk can go from to in one step. The adjacency matrix of is the matrix with -entries such that
and its transpose is the non-backtracking matrix of introduced by Hashimoto [16]. Moreover, a random walk on is precisely a non-backtracking random walk on . Since each vertex of has (out-)degree
the random walk Laplacian of is well-defined, and it is called the non-backtracking Laplacian of . It can be written as
where denotes the identity matrix, is the degree matrix of and has diagonal entries
and is the transition probability matrix of the non-backtracking random walk on .
We introduced the non-backtracking Laplacian in [17], together with J. Jost. Its spectral properties were further investigated in [26], its connection to graph colorings was studied in [24], and it has been applied to vertex clustering in [6]. The computations in [17 Table 2] showed that, among graphs with at most ten nodes and minimum degree at least 2, substantially fewer graphs admit a cospectral mate for the non-backtracking Laplacian than for the other operators considered; that is, there are fewer pairs of non-isomorphic graphs with the same spectrum. Moreover, in the same paper we showed that the presence of certain cycle configurations produces real eigenvalues of .
For the non-backtracking matrix, the Ihara–Bass formula [4, 30, 19],
where and are the adjacency and degree matrices of , gives at least real eigenvalues for each of and , counted with algebraic multiplicity. If is –regular, then
Therefore, in this case, also has at least real eigenvalues, counted with algebraic multiplicity. For irregular graphs, however, degree normalization does not act by a scalar rescaling, and the Ihara–Bass formula does not directly give a corresponding lower bound for . It is therefore natural to ask whether the lower bound nevertheless holds for the non-backtracking Laplacian. Motivated by numerical experiments, we conjectured in 2022 that always has at least real eigenvalues, counted with algebraic multiplicity. We formulated this conjecture during our course on non-backtracking operators of graphs at the Max Planck Institute for Mathematics in the Sciences, and it was later stated as an open problem in [25 Exercise 13].
Here we prove this conjecture, and we refine it as follows.
Theorem (Theorem 4.1 and Corollary 5.2). Let be a simple graph on nodes and edges, with minimum degree at least 2. Let be the number of connected components of , and let be the number of bipartite ones. Then, the number of real eigenvalues of the non-backtracking Laplacian of , counted with algebraic multiplicity, is at least
Moreover, this bound is sharp.
For connected regular graphs, we also determine exactly when the above bound is attained. Recall that a connected –regular graph is Ramanujan [21, 27] if every adjacency eigenvalue satisfies
We call it strictly Ramanujan if every adjacency eigenvalue satisfies
We show that, for a connected regular graph , the non-backtracking Laplacian has exactly real eigenvalues if and only if is strictly Ramanujan. In particular, cycles, complete graphs and balanced complete bipartite graphs, which are strictly Ramanujan, attain the bound.
We also determine how these real eigenvalues are distributed around 1. In Theorem 6.2, we show that at least of them lie in and at least lie in .
For completeness, we also prove in Theorem 7.1 that has at most real eigenvalues, counted with algebraic multiplicity, and that this bound is attained by the cycle .
Structure of the paper
In Section 2, we fix the notation and establish some preliminary results, including Lemma 2.2 from indefinite linear algebra. In Section 3, we prove Theorem 3.1, which settles our 2022 conjecture. In Section 4, we refine this bound by taking into account the connected and bipartite components of the graph, thus proving Theorem 4.1. In Section 5, we show that the refined bound is sharp, and we prove that a connected regular graph attains it if and only if it is strictly Ramanujan. In Section 6, we show how the real eigenvalues split around 1. Finally, in Section 7, we prove an upper bound on the number of real eigenvalues of the non-backtracking Laplacian.
Notation and preliminaries
Throughout the paper, we fix a simple graph on nodes and edges, with minimum degree at least 2, and we use the same notation as in the introduction. In particular, denotes the non-backtracking graph of , whose vertices are the oriented edges of , labeled so that
Moreover, and denote the adjacency and degree matrices of , while and denote the non-backtracking Laplacian and the transition matrix of the non-backtracking random walk on .
We identify each vector with the function
In these terms, the transition matrix acts as
for every , where means that and are adjacent in .
Given a real symmetric matrix , the -product on is defined as
where is the standard inner product on . A matrix is said to be self-adjoint with respect to the -product, or -self-adjoint, if
or equivalently, if
As in [17], we let be the matrix
where each block has size . Since , we have that
for each . Moreover, by [17 Theorem 3.8], is -self-adjoint, that is,
We now introduce the matrix
Its entries are
In particular, is real and symmetric. Moreover, is -self-adjoint. In fact, by (3) and since commutes with ,
The matrix plays a central role in the proofs of our main results, for the following reason. By Lemma 2.2 below, if a real matrix is self-adjoint with respect to the -product of a real symmetric invertible matrix , then has at most non-real eigenvalues, where and denote the numbers of positive and negative eigenvalues of , counted with multiplicity. By (3), is -self-adjoint. However, has eigenvalues and , each with multiplicity , so in this case the lemma only says that has at most non-real eigenvalues, which is trivial since is a matrix. The advantage of considering is that is also -self-adjoint, by (4), and has only positive eigenvalues and negative ones, by Lemma 2.1 below. Since every vertex of has degree at least 2, we have that
and therefore
Hence, by Lemma 2.2, has at most non-real eigenvalues, that is, at least real ones. This is the content of Theorem 3.1. For the refinement in Theorem 4.1, we then use the connected and bipartite components of to reduce the number of positive eigenvalues of that need to be taken into account.
We first prove the claim on the eigenvalues of .
Lemma 2.1. The matrix is invertible. Moreover,
Proof. By definition of , we have that whenever . Hence, if we order the oriented edges according to their input, is block diagonal, with one block of size for each . Moreover,
where denotes the matrix whose entries are all equal to 1. Since has eigenvalue with multiplicity 1, and eigenvalue 0 with multiplicity , the block has eigenvalue 1 with multiplicity 1, and eigenvalue with multiplicity . The eigenvalues of , with multiplicity, are those of the blocks . Since none of them is zero, is invertible, and
We now state the linear algebra fact used in the proofs of our main results. Given a real square matrix , we let denote the number of real eigenvalues of , counted with algebraic multiplicity.
Lemma 2.2. Let be symmetric and invertible, and let be -self-adjoint. Then, has at most non-real eigenvalues, counted with algebraic multiplicity. Equivalently,
Proof. Since is -self-adjoint, it follows from [14 page 77] (see the inequality following equation (5.2.4) and the comment after it, where , and in our notation) that is at least half the number of non-real eigenvalues of , counted with algebraic multiplicity. Since is also -self-adjoint, and since , the same holds for . Therefore, the number of non-real eigenvalues of is at most .
The bound
In this section, we prove our 2022 conjecture, which states that the non-backtracking Laplacian of a graph with minimum degree at least 2 has at least real eigenvalues. As anticipated in § 2, this follows by combining the -self-adjointness of with Lemma 2.1 and Lemma 2.2.
Theorem 3.1. Let be a simple graph on nodes and edges, with minimum degree at least 2. Then, the number of real eigenvalues of the non-backtracking Laplacian of , counted with algebraic multiplicity, is at least
Proof. By (4), is -self-adjoint, and by Lemma 2.1, is a real symmetric invertible matrix with and . As observed in (5), the minimum degree assumption implies that
Applying Lemma 2.2 with and yields
The refined bound
In this section, we refine Theorem 3.1 by taking into account the connected and bipartite components of . These give explicit eigenvectors of with real eigenvalues, which allow us to reduce the number of positive eigenvalues of that need to be taken into account in Lemma 2.2.
Theorem 4.1. Let be a simple graph on nodes and edges, with minimum degree at least 2. Let be the number of connected components of , and let be the number of bipartite ones. Then, the number of real eigenvalues of the non-backtracking Laplacian of , counted with algebraic multiplicity, is at least
Proof. For each connected component of , let be the vertex set of , let be its edge set, and let be the indicator function of the oriented edges of $C. If is bipartite, fix a function that takes opposite values on adjacent vertices, and let
By (2) we have that, for every ,
Hence, . Similarly, for every , by definition of , and since and belong to the same connected component,
Hence, . Moreover, if is bipartite and is in , then . Since each oriented edge with also belongs to , this implies that, by (2),
and by definition of ,
Together with the fact that both and vanish outside , this implies that
Since and , from the above equalities it follows that
Now, let be the span of the functions , for all connected components , and , for all bipartite components . These functions are non-zero and mutually orthogonal with respect to the standard inner product. In fact, functions associated with different components have disjoint supports, and for a bipartite component ,
Therefore, . Moreover, for every , and since is spanned by eigenvectors of , it is -invariant, that is, for every .
Now, for all and , we have that
where the second equality holds because is symmetric, the third because is real, and the fourth because .
Therefore, if we let be the orthogonal complement of with respect to the standard inner product, then is also -invariant. In fact, let and . Then, since , we have that
where the first and third equalities follow from the above identity, the second one holds because is -self-adjoint, and the last one because . Hence, .
Now, let be a real orthogonal matrix whose first columns are the vectors , whose next columns are the vectors , and whose remaining columns form an orthonormal basis of , which can be chosen real since is spanned by real vectors. In other words, is the change of basis to an orthonormal basis adapted to the decomposition . Since both summands are -invariant, is block diagonal, and since the first columns of are eigenvectors of , with eigenvalue for the first ones and for the next ones,
where is the diagonal matrix with diagonal entries equal to and diagonal entries equal to , and is a real matrix of size .
Similarly, let denote the -th column of . Then , and by the identity above, , which is if and otherwise, whenever or . Hence
where is a real symmetric matrix of size .
Since is invertible, so is . Moreover, by Sylvester’s law of inertia and Lemma 2.1,
and
Since , the identity implies that
and comparing the lower right blocks gives . That is, is -self-adjoint. By (5), we have that
and therefore Lemma 2.2 implies that has at most non-real eigenvalues, counted with algebraic multiplicity.
Finally, since is block diagonal,
Hence, every non-real eigenvalue of is an eigenvalue of , with the same algebraic multiplicity, and therefore
Sharpness
In this section, we show that the bound in Theorem 4.1 is sharp. For connected regular graphs, we first determine exactly when it is attained: by Theorem 5.1, this happens if and only if the graph is strictly Ramanujan. As a consequence, in Corollary 5.2 we obtain several explicit families of graphs attaining the bound.
Theorem 5.1. Let be a connected -regular graph with , and let be the number of adjacency eigenvalues of with , counted with multiplicity. Then,
In particular, equality in Theorem 4.1 holds if and only if is strictly Ramanujan, that is, every adjacency eigenvalue satisfies .
Proof. Let be a connected -regular graph on nodes and edges, with . Since is connected, we have that , and therefore the quantity in Theorem 4.1 is
where if is bipartite, and otherwise.
Now, let be the eigenvalues of the adjacency matrix of , listed with multiplicity, and given , let
Since is -regular, we have that and
Hence, the Ihara–Bass formula (1) becomes
For , substituting and multiplying both sides by , we obtain
Note that the exponent is non-negative. We now count the real roots of each factor, with multiplicity.
The first factor has real roots, namely and , each with multiplicity .
Since is connected and -regular, is a simple eigenvalue of . Moreover, is an eigenvalue of if and only if is bipartite, in which case it is also simple. The corresponding quadratic factors are
which have two real roots each. Hence, the eigenvalues contribute real roots.
For every other eigenvalue of , the discriminant of is
Therefore, has two real roots, counted with multiplicity, if , and two non-real roots if .
Since the multiplicities of the roots add up when polynomials are multiplied, we obtain, with as in the statement,
Since , this implies that
In particular, has exactly real eigenvalues if and only if , that is, if and only if is strictly Ramanujan.
Corollary 5.2. The bound in Theorem 4.1 is attained by the following graphs:
the cycle graph , for every ;
the complete graph , for every ;
the complete bipartite graph , for every .
In particular, the bound in Theorem 4.1 is sharp.
Proof. Since all these graphs are connected and regular, by Theorem 5.1 it suffices to show that they are strictly Ramanujan.
The cycle is -regular, and its adjacency eigenvalues are , for . All of them except satisfy .
The complete graph is -regular, and its only adjacency eigenvalue other than is , which satisfies for .
The complete bipartite graph is -regular, and its only adjacency eigenvalue other than is , which satisfies for .
This proves the claim.
Splitting the real eigenvalues around 1
Theorem 4.1 counts the real eigenvalues of . In this section, we show how many of them must lie on each side of . Equivalently, we count the positive and the negative real eigenvalues of .
Recall from [17 Theorem 4.1] that every eigenvalue of satisfies
where is the largest degree of . Hence, the real eigenvalues of in actually lie in , and those in lie in .
For a real symmetric matrix , we define its signature as
For a real square matrix , we let and denote the numbers of positive and negative real eigenvalues of , counted with algebraic multiplicity.
The following lemma, which refines Lemma 2.2, is needed for the proof of Theorem 6.2 below.
Lemma 6.1. Let be symmetric and invertible, and let be invertible and -self-adjoint. Then,
Proof. The matrix is real, symmetric and invertible, since
By the canonical form for -self-adjoint matrices [14 Theorem 5.1.1], there is an invertible matrix such that and are block diagonal with matching blocks, as follows. Each Jordan block of a real eigenvalue is paired with , where is the matrix with ones on the anti-diagonal and zeros elsewhere, and . Each pair of Jordan blocks of a non-real eigenvalue is paired with . Since
the matrices and are block diagonal, and by Sylvester’s law of inertia their signatures are the sums of the signatures of the blocks. The symmetric matrix has signature if is odd and if is even, and so does multiplied by , for real . For a pair of non-real eigenvalues, both blocks have signature , since the span of the first basis vectors of the block is isotropic for both forms and has half the dimension. Therefore
where both sums run over the Jordan blocks of odd size belonging to real eigenvalues . Let and be the sums of over such blocks with and with , respectively. Then, and . Finally, is at most the number of blocks with , which is at most , and similarly .
Using Lemma 6.1, we can now refine Theorem 4.1 as follows.
Theorem 6.2. Let be a simple graph on nodes and edges, with minimum degree at least . Let be the number of connected components of , and let be the number of bipartite ones. Then, has at least positive and at least negative real eigenvalues, counted with algebraic multiplicity. Equivalently, has at least real eigenvalues in and at least real eigenvalues in .
Proof. We use the notation of the proof of Theorem 4.1. Let , so that is block diagonal with blocks and , and has blocks and .
Since and , the matrix maps to itself, and since is symmetric, it also maps to itself. Hence is block diagonal, with a diagonal first block having entries equal to and entries equal to , and a second block . Comparing the second blocks in
and in (3) gives
and
The matrix has eigenvalues and , each with multiplicity . By Sylvester’s law of inertia, and , and from the proof of Theorem 4.1, and . Hence,
Since is invertible, so is . Lemma 6.1 with and gives
and
where we used . Finally, the first block contributes the eigenvalue with multiplicity and the eigenvalue with multiplicity . The statement for follows from and the fact that all eigenvalues of have modulus at most , since is row-stochastic.
Adding the two bounds of Theorem 6.2 gives Theorem 4.1. Both bounds are attained by the strictly Ramanujan graphs of Theorem 5.1: in the proof of that theorem, the factor
contributes positive and negative roots, the eigenvalue of contributes the positive roots and , and the eigenvalue , present exactly when is bipartite, contributes the negative roots and .
Remark 6.3. The results of this section do not depend on the particular weights , and they hold for any weighted matrix , where is a positive function on the vertices and is the diagonal matrix with diagonal entries . In fact, as in Lemma 2.1, is symmetric with positive and negative eigenvalues, therefore Lemma 6.1 shows that has at least positive and at least negative real eigenvalues. The refinement by and can also be obtained, using the Perron–Frobenius Theorem in place of the explicit eigenvectors and . In particular, corresponds to , while gives the transpose of the non-backtracking matrix. Note, however, that the location of the real eigenvalues of in and uses the fact that is row-stochastic, and it does not extend to arbitrary weights.
An upper bound
We now complement Theorem 4.1 with an upper bound on the number of real eigenvalues of .
Theorem 7.1. Let be a simple graph on nodes and edges, with minimum degree at least . Let be the number of connected components of , and let be the number of bipartite ones. Then, the number of real eigenvalues of the non-backtracking Laplacian of , counted with algebraic multiplicity, is at most
Moreover, this bound is attained by the cycle .
Proof. Since , it suffices to show that has at least non-real eigenvalues, counted with algebraic multiplicity.
If we order the oriented edges of according to the connected components of , then is block diagonal, with one block for each connected component , and is the transition matrix of the non-backtracking random walk on . Hence, it suffices to show that each has at least two non-real eigenvalues, and at least four if is bipartite. To this end, we use the following three facts.
(i) All eigenvalues of are non-zero. In fact, is invertible, since and is invertible by Lemma 2.1, and the eigenvalues of are eigenvalues of .
(ii) Since is row-stochastic, all eigenvalues of satisfy . Moreover, for the same reason, is an eigenvalue of , with the constant functions as eigenfunctions.
(iii) We have that . In fact,
where and range over the oriented edges of . If , then both factors are non-zero, that is, a non-backtracking random walk can go from to and from to . The first step requires to start at the output of , and the second one requires to end at the input of , therefore . But the step from to is excluded by the definition of a non-backtracking random walk. Hence, all terms in the above sum vanish.
Now, let be the eigenvalues of , listed with algebraic multiplicity. Then, by (iii),
By (i), every real eigenvalue of satisfies . Hence, by (6), has at least one non-real eigenvalue. Since is real, its non-real eigenvalues appear in complex conjugate pairs, and therefore has at least two non-real eigenvalues.
Now, assume that is bipartite. Let denote the vertex set of , and let denote the number of edges of . We want to show that, in this case, cannot have exactly one pair of complex conjugate non-real eigenvalues. Since is bipartite, there exists a function that takes opposite values on adjacent vertices. Hence, we can define the diagonal matrix with diagonal entries
for each oriented edge of $C. If , then a non-backtracking random walk can go from to , implying that , and therefore . Therefore, since is diagonal, for all oriented edges of we have that
where the last equality follows from the previous observation if , and is trivial if . Hence,
Since , it follows that and are similar, and therefore the eigenvalues of , with multiplicity, are invariant under . In particular, since is an eigenvalue of by (ii), so is .
Now assume, by contradiction, that has exactly two non-real eigenvalues, and . By the above invariance, is also a non-real eigenvalue of , therefore . Since by (i), we have that , and therefore . This means that is purely imaginary, that is, for some with . Moreover, by (ii).
We now separate, in (6), one copy of the eigenvalue , one copy of the eigenvalue , and the two eigenvalues and . Denoting by the set of indices of the remaining eigenvalues, which are all real, we obtain
Since , we have that , and by (i), for every . Hence, both and the sum over must vanish, that is, and . Therefore, the only eigenvalues of are , , , and , each with multiplicity one. Since is a matrix, this implies that . However, since every vertex of has degree at least , we have
implying that . This is a contradiction, and therefore has at least four non-real eigenvalues.
Finally, for the cycle , we have that and , therefore
Together with Theorem 4.1, this shows that has exactly real eigenvalues, and that the bound is attained.
Declaration of AI assistance
The proofs presented in this paper were developed with the assistance of ChatGPT-6.1 Sol (OpenAI) and Claude Opus 5.5 (Anthropic). All proofs were checked in detail by the authors, who take full responsibility for the content.
Funding
Raffaella Mulas is supported by the Dutch Research Council (NWO) through the grant VI.Veni.232.002 (Grant ID: https://doi.org/10.61686/NLUFV33835).
References
- [1]F. Arrigo, D.J. Higham, and V. Nof erini. Beyond non-backtracking: non-cycling network centrality measures. Proceedings. Mathematical, Physical, and Engineering Sciences, 476, 2020.DOI
- [2]F. Arrigo, D.J. Higham, V. Noferini, and R. Wood. Weighted enumeration of nonbacktracking walks on weighted graphs. SIAM Journal on Matrix Analysis and Applications, 45(1):397–418, 2024.arxiv.org/abs/2202.02888
- [3]Á. Backhausz, B. Szegedy, and B. Virág. Ramanujan graphings and correlation decay in local algorithms. Random Structures & Algorithms, 47(3):424–435, 2015.DOI
- [4]H. Bass. The Ihara-Selberg zeta function of a tree lattice. International Journal of Mathematics, 3(06):717–797, 1992.DOI
- [5]M. Bolla. The non-backtracking random walk and its usage for vertex clustering. arXiv preprint arXiv:2512.24434, 2025.arxiv.org/abs/2512.24434
- [6]M. Bolla, H. Reittu, and F. Abdelkhalek. Clustering the nodes of sparse edge-weighted graphs via non-backtracking spectra. In Future of Information and Communication Conference, pages 81–99. Springer, 2025.DOI
- [7]C. Bordenave, M. Lelarge, and L. Massoulié. Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs. Annals of probability: An official journal of the Institute of Mathematical Statistics, 46(1):1–71, 2018.
- [8]A.E. Brouwer and W.H. Haemers. Spectra of graphs. Springer Science & Business Media, 2011.
- [9]C. Castellano and R. Pastor-Satorras. Relevance of backtracking paths in recurrent-state epidemic spreading on networks. Physical Review E, 98(5):052313, 2018.DOI
- [10]F. Chung. Spectral graph theory. American Mathematical Soc., 1997.
- [11]Y. Cooper. Properties determined by the Ihara zeta function of a graph. The Electronic Journal of Combinatorics, 16(1):R84, 2009.DOI
- [12]S. Coste and Y. Zhu. Eigenvalues of the non-backtracking operator detached from the bulk. Random Matrices: Theory and Applications, 10(03):2150028, 2021.DOI
- [13]C. Glover and M. Kempton. Some spectral properties of the non-backtracking matrix of a graph. Linear Algebra and its Applications, 618:37–57, 2021.DOI
- [14]I. Gohberg, P. Lancaster, and L. Rodman. Indefinite linear algebra and applications. Springer Science & Business Media, 2006.DOI
- [15]P. Grindrod, D.J. Higham, and V. Noforini. The Deformed Graph Laplacian and Its Applications to Network Centrality Analysis. SIAM Journal on Matrix Analysis and Applications, 39(1):310–341, 2018.DOI
- [16]K. Hashimoto. Zeta functions of finite graphs and representations of p-adic groups. In Automorphic Forms and Geometry of Arithmetic Varieties, volume 15 of Advanced Studies in Pure Mathematics, pages 211–280. Elsevier, 1989.
- [17]J. Jost, R. Mulas, and L. Torres. Spectral theory of the non-backtracking Laplacian for graphs. Discrete Mathematics, 346(10):113536, 2023.DOI
- [18]J. Jost, R. Mulas, and D. Zhang. Spectra of Discrete Structures. Number 221 in Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2026.DOI
- [19]M. Kempton. Non-backtracking random walks and a weighted Ihara’s theorem. Open Journal of Discrete Mathematics, 6(4):207–226, 2016.arxiv.org/abs/1603.05553
- [20]F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborová, and P. Zhang. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences, 110(52):20935–20940, 2013.DOI
- [21]A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261–277, 1988.
- [22]T. Martin, X. Zhang, and M.E.J. Newman. Localization and centrality in networks. Physical Review E, 90(5):052808, 2014.DOI
- [23]A. Mellor and A. Grusovin. Graph comparison via the nonbacktracking spectrum. Phys. Rev. E, 99:052309, May 2019.DOI
- [24]R. Mulas. Maximal colourings for graphs. Graphs and Combinatorics, 40(93), 2024.arxiv.org/abs/2307.10910
- [25]R. Mulas. Spectral theory of graphs and hypergraphs. Lecture notes for the BeyondTheEdge MSCA Doctoral Network, Marseille, France, 2025. Available at https://cdn.prod.website-files.com/673b1c6a31679f06b3ecf571/68d3daeb1b89a52be5dee00e_Marseille-LectureNotes-RM.pdf (Accessed October 2026).
- [26]R. Mulas, D. Zhang, and G. Zucal. There is no going back: Properties of the non-backtracking Laplacian. Linear Algebra Appl., 680:341–370, 2024.arxiv.org/abs/2303.00373
- [27]M.R. Murty. Ramanujan graphs. Journal of the Ramanujan Mathematical Society, 18(1):33–52, 2003.
- [28]R. Pastor-Satorras and C. Castellano. The localization of non-backtracking centrality in networks and its physical consequences. Scientific reports, 10(1):1–12, 2020.
- [29]M. Shrestha, S.V. Scarpino, and C. Moore. Message-passing approach for recurrent-state epidemic models on networks. Physical Review E, 92(2):022821, 2015.pubmed.ncbi.nlm.nih.gov/26382468
- [30]A. Terras. Zeta functions of graphs: A stroll through the garden, volume 128 of Cambridge studies in advanced mathematics. Cambridge University Press, 2010.DOI
- [31]L. Torres, K.S. Chan, H. Tong, and T. Eliassi-Rad. Nonbacktracking eigenvalues under node removal: X-centrality and targeted immunization. SIAM Journal on Mathematics of Data Science, 3(2):656–675, 2021.DOI
- [32]L. Torres, P. Suárez-Serrato, and T. Eliassi-Rad. Non-backtracking cycles: length spectrum theory and graph mining applications. Applied Network Science, 4(1):1–35, 2019.DOI