Background
----------


For a finite graph $G$, let $\tilde{G}$ denote the [universal cover](https://en.wikipedia.org/wiki/Covering_graph#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](https://en.wikipedia.org/wiki/Biregular_graph), 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.



Can we calculate the spectral radius of the universal cover for specific graphs?
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.


