On the growth rate of the universal covering tree
This work studies the relation between two graph parameters, ρ and Λ.
For an undirected graph G, ρ(G) is the growth rate of its universal cover,
while Λ(G) is the weighted geometric average of the vertex degree minus one,
where the vertex weights are proportional to the degree.
It is well known that ρ(G) ≥ Λ(G).
Graphs satisfying the equality, ρ(G) = Λ(G), are those for which the following statements are true:
1.
For a random lift of G, the mixing time of the non-backtracking random walk (NBRW) is the same as its diameter
up to (1 + o(1)) factor with high probability.
2.
The Moore bound for lifts of G is the same as the Moore bound for graphs which have the same degree distribution as G,
where the Moore bound is the best known lower bound on the size of a girth g graph, for a given graph family.
This work derives a necessary and sufficient condition for the equality to hold.
A non-backtracking path P in G is called a suspended path if all its internal vertices have degree two, while its endpoints have larger degree.
We prove that ρ(G) = Λ(G) iff every suspended path P in G satisfies the equality
(deg(v) - 1)(deg(u) - 1) = Λ(G)^{2l}, where u and v are the endpoints of P and l is its length.
Graphs with ρ = Λ include regular graphs and bipartite-biregular graphs, possibly with replacement of all edges by a length k path.
As a consequence of our result, we give an infinite family of graphs with ρ = Λ that are not in the above list.