In this paper we take a very special model of a random non-regular graph and study its non-backtracking spectrum. We study graphs consisting of a cycle with some random loops added; the graphs are not regular and their non-backtracking spectrum does not seem to be confined to some one-dimensional set in the complex plane. The non-backtracking spectrum is required in some applications, and has no straightforward connection to the usual adjacency matrix spectrum for general graphs, unlike the situation for regular graphs. Experimentally, the random graphs' spectrum appears similar in shape to its deterministic counterpart, but differs because the eigenvalues are visibly clustered, especially with a mysterious gap around Re(l)=1.
Joel Friedman, Department of Computer Science and Mathematics, University of British Columbiajf@cs.ubc.ca
"Eigenvalues of Non-Backtracking Walks in a Cycle with Random Loops,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 8
, Article 10.
Available at: http://scholar.rose-hulman.edu/rhumj/vol8/iss2/10