Girth and subdominant eigenvalues for stochastic matrices.
PageRank is a ranking method that assigns scores to web pages using the limit distribution of a random walk on the web graph. A fibration of graphs is a morphism that is a local isomorphism of in-neighbourhoods, much in the same way a covering projection is a local isomorphism of neighbourhoods. We show that a deep connection relates fibrations and Markov chains with restart, a particular kind of Markov chains that include the PageRank one as a special case. This fact provides constraints on the...
Let be a square -matrix. Then is a Hall matrix provided it has a nonzero permanent. The Hall exponent of is the smallest positive integer , if such exists, such that is a Hall matrix. The Hall exponent has received considerable attention, and we both review and expand on some of its properties. Viewing as the adjacency matrix of a digraph, we prove several properties of the Hall exponents of line digraphs with some emphasis on line digraphs of tournament (matrices).