Can we calculate the spectral radius of the universal cover for specific graphs?

Question

Background

For a finite graph $G$, let $\tilde{G}$ denote the universal cover of $G$. For a vertex $v$, let $p_{2n}(v)$ denote the number of paths of length $2n$ that start and end at $v$. The spectral radius of $\tilde{G}$, denoted $\rho(\tilde{G})$, is equal to $$ \rho(\tilde{G})=\lim_{n\rightarrow\infty} p_{2n}(v)^{\frac{1}{2n}} $$ for any vertex $v\in\tilde{G}$.

Known Examples:

For some graphs, the combinatorics of counting pathes simplifies greatly. For $d$-regular graphs, the cover is the $d$-regular tree, and the spectral radius of the universal cover, the $d$-regular tree, equals $2\sqrt{d-1}$.

For biregular graphs, with degrees $d_1,d_2$, calculating the number of paths can be similarly done, and the universal cover has radius $\sqrt{d_1-1}+\sqrt{d_2-1}$.

Question

Can we explicitly calculate the radius of the universal cover for other irregular graphs? I couldn't find any explicit examples in the literature other than the two mentioned above.

I would specifically like to know how to calculate it for the following two cases:

1. Let $G_1$ denote $K_4$ minus an edge. What is $\rho(\tilde{G}_1)$? Numerically, it is around $~2.508\dots $

2. Let $G_2$ denote $K_5$ minus an edge. What is $\rho(\tilde{G}_2)$? Numerically, it is around $~3.262\dots $

The problem I run into when trying to calculate the number of paths in $\tilde{G}_1$ is that backtracking changes the distribution of vertices, potentially in a complicated way with multiple backtracks, but I might be missing something.

Answer 1

For the complete graph minus an edge $K_n-e$, the spectral radius is the largest zero of \begin{align*}&x^{14}+(30-10 n) x^{12}+(2 n^{3}+21 n^{2}-202 n +357) x^{10}\\ &+(-10 n^{4}+26 n^{3}+456 n^{2}-2288 n +2888) x^{8} \\ &+(n^{6}-4 n^{5}+76 n^{4}-1520 n^{3}+9320 n^{2}-23056 n +20360) x^{6}\\ &+(-4 n^{7}+48 n^{6}-272 n^{5}+2184 n^{4}-16472 n^{3}+66016 n^{2}-126496 n +93120) x^{4}\\ & +(4 n^{8}-80 n^{7}+720 n^{6}-4432 n^{5}+22800 n^{4}-91712 n^{3}+242704 n^{2}-358944 n +222672) x^{2}\\ & -16 (n -4)^{3} (n^{2}-6 n +10)^{3}. \end{align*} Values for $n=4,5,6,7,8$: 2.50828679, 3.26287647, 3.85572357, 4.36125025, 4.80992000. Experimentally, it is very close to $2\sqrt{n-2}$.

I confess to not tying up every last bit of the proof, but at least the method is valid. Label $K_n-e$ as $0,1,\ldots,n-1$ where $\{0,1\}$ is the missing edge. Apply the labelling to the cover.

For a vertex $v_i$ labelled $i$ in the cover, and neighbour $v_j$ labelled $j$, let $w_{ij}=w_{ij}(x)$ be the ordinary generating function for closed walks that start at $v_i$, step to $v_j$, then do anything they like except that they only return to $v_i$ in the last step. Because $K_n-e$ is so symmetrical, there are only 3 values for this generating function, represented by $w_{02},w_{20},w_{23}$. Also let $w_0$ be the ogf for all closed walks starting at $v_0$. We can write relations between them: $$ w_{02} = \frac{x^2}{1-w_{20}-(n-3)w_{23}},\quad w_{20} = \frac{x^2}{1-(n-3)w_{02}}, $$ $$ w_{23} = \frac{x^2}{1-2w_{20}-(n-4)w_{23}} \quad w_0 = \frac{1}{1-(n-2)w_{02}}. $$ These equations can be solved for $w_0$, though I didn't find any way to write the solution in a pretty form. It satisfies a quartic polynomial with coefficients that are polynomial in $n,x$.

The final step is to identify the smallest singularity (which is on the real line since all the coefficients are non-negative). The reciprocal of that is the spectral radius.

ADDED Nov 19, 2023:

This paper that just appeared on the arXiv is very much related to this question.

Answer 2

An algorithm to compute the spectral radius of the universal cover of a given finite graph is proposed in the paper below. It does not look very practical though.

• Nagnibeda, Tatiana. "Random walks, spectral radii, and Ramanujan graphs." Random walks and geometry (2004): 487-500.