Skip to main content
MathOverflow

Return to Question

Added the first few digits of the numerical approximation for k5 minus edge.
Source Link
Eric Naslund
Eric Naslund
  • 11.4k
  • 1
  • 66
  • 106

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.

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 $~2.508\dots $

  2. Let $G_2$ denote $K_5$ minus an edge. What is $\rho(\tilde{G}_2)$?

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.

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.

added 69 characters in body
Source Link
Eric Naslund
Eric Naslund
  • 11.4k
  • 1
  • 66
  • 106

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.

SpecificallyI 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 $~2.508\dots $

  2. Let $G_2$ denote $K_5$ minus an edge. What is $\rho(\tilde{G}_2)$?

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.

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.

Specifically:

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

  2. Let $G_2$ denote $K_5$ minus an edge. What is $\rho(\tilde{G}_2)$?

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.

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 $~2.508\dots $

  2. Let $G_2$ denote $K_5$ minus an edge. What is $\rho(\tilde{G}_2)$?

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.

Source Link
Eric Naslund
Eric Naslund
  • 11.4k
  • 1
  • 66
  • 106

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

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.

Specifically:

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

  2. Let $G_2$ denote $K_5$ minus an edge. What is $\rho(\tilde{G}_2)$?

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.