## Theses and Dissertations

#### Abstract

This thesis studies two problems centered around non-backtracking walks on graphs. First, we analyze the spectrum of the non-backtracking matrix of a graph. We show how to obtain the eigenvectors of the non-backtracking matrix using a smaller matrix and in doing so, create a block diagonal decomposition which more clearly expresses the non-backtracking matrix eigenvalues. Additionally, we develop upper and lower bounds on the matrix spectrum and use the spectrum to investigate properties of the graph. Second, we investigate the difference between PageRank and non-backtracking PageRank. We show some instances where there is no difference and develop an algorithm to compare PageRank and non-backtracking PageRank under certain conditions using $\mu$-PageRank.

MS

Mathematics

2021-07-15

Thesis

#### Handle

http://hdl.lib.byu.edu/1877/etd11832

#### Keywords

graph theory, combinatorics, random walks, non-backtracking random walks, non-backtracking spectrum, pagerank

english

COinS