Any source to find distance between vertices in generalized Petersen graphs?

Question

I am trying to find the distance between vertices of generalized Petersen graphs $P(n,k)$. For $n = 50$ and $k<\frac{n}{2}$ I did everything manually. I manually wrote down a shortest path between any two vertices. However, it is really cumbersome to find the same for higher values of $n$. Is there any site/software/link to find a shortest distance between vertices of generalized Petersen graphs? I will be really grateful for the help. Thanks for the help.

P.S. I tried Mathematica with the help of a friend and got to know that I can get radius and diameter using this. But I am interested in the shortest paths. The generalized Petersen graphs $P(n,1)$ and generalized Petersen graphs $P(n,2)$ are shown below.

Answer 1

Use the fact that the vertices lie on a circle, so you can compute the coordinates easily. If the vertices on the inner polygon are on a circle of radius $r$, they are at $(r \cos \frac {2m\pi}n, r\sin \frac {2m\pi}n)$ for $m=0,1,2,\ldots n-1$. The outer polygon has radius $R$, so make the substitution. Now computing the distance is easy. The distances between the two sets of vertices are just $R-r$. The distance for the chords of the inner polygon are $r\sqrt {(1-\cos \frac {2k\pi}n)^2+\sin^2 \frac {2k\pi}n}$. The distance for the chords on the outer polygon is $R\sqrt {(1-\cos \frac {2\pi}n)^2+\sin^2 \frac {2\pi}n}$

For your $P(n,2)$ example I was considering the inner edges, like from $u_1$ to $u_3,$ to be straight. The edge between a $u$ and a $v$ has length $R-r$. The edge between two $v$s has length $R\sqrt {(1-\cos \frac {2\pi}n)^2+\sin^2 \frac {2\pi}n}$ and the edge between two $u$s has length $r\sqrt {(1-\cos \frac {4\pi}n)^2+\sin^2 \frac {4\pi}n}$. The $v$s are neighboring points on a circle divided into $n$ equal segments. The $u$s are separated by $1$, which accounts for the extra factor $2$ in the angles.

Answer 2

Please note that we can readily compute several quantities from the diagram. Two most important quantities are the length of the arc, $s = r\theta$ and the length of the chord, $c = 2r \sin \frac{\theta}{2}$

Once we know these two quantities, the rest of the job is easy. For shortest path computation, we need to know the length of the edges of the graph. Here the lengths may be computed using simple formulas.

For example, consider the graph P(4,1)

Two inner/outer vertices are either connected by a chord or by an arc. An outer and an inner vertex are connected by a straight line. So in all the cases, the length of the edges are known. Now the rest should be easy if you use some standard algorithm like Dijkstra's algorithm. Many such algorithms are available here

Let me cite an example using P(4, 1) following your naming convention. Assume that the outer vertices are $u_0, u_1, u_2, u_3$ and the corresponding inner vertices are $v_0, v_1, v_2, v_3$

Now if you want to compute the shortest path between any two vertices $a$ and $b$, then there can be only three cases:

1. They both are of type $u$
2. They both are of type $v$
3. One of them is of type $u$ and the other one is of type $v$

The graph has $8$ vertices and $12$ edges. Note that we do not have any arcs as our edges. Let us assume that the radius of the inner circle is $r$ and the radius of the outer circle is $R$. Then there are only three types of edges: Distance between two vertices of type $u$ is $e_1 = \sqrt{2}R$, Distance between two vertices of type $v$ is $e_2 = \sqrt{2}r$ and the edges connecting $u$ and $v$ are of length $e_3 = (R-r)$

Here is the adjacency matrix:

\begin{array}{c|cccccccc} \text{vertices} & u_0 & u_1 & u_2 & u_3 & v_0 & v_1 & v_2 & v_3\\ \hline u_0 & 0 & e_1 & 0 & e_1 & e_3 & 0 & 0 & 0\\ u_1 & e_1 & 0 & e_1 & 0 & 0 & e_3 & 0 & 0\\ u_2 & 0 & e_1 & 0 & e_1 & 0 & 0 & e_3 & 0\\ u_3 & e_1 & 0 & e_1 & 0 & 0 & 0 & 0 & e_3\\ v_0 & e_3 & 0 & 0 & 0 & 0 & e_2 & 0 & e_2\\ v_1 & 0 & e_3 & 0 & 0 & e_2 & 0 & e_2 & 0\\ v_2 & 0 & 0 & e_3 & 0 & 0 & e_2 & 0 & e_2\\ v_3 & 0 & 0 & 0 & e_3 & e_2 & 0 & e_2 & 0 \end{array}

As an illustration, I set $R = \sqrt{2}$, $r = \frac{1}{\sqrt{2}}$ and computed all the pair-wise shortest paths using Floyd-Warshall algorithm.

\begin{array}{c|cccccccc} \text{distances} & u_0 & u_1 & u_2 & u_3 & v_0 & v_1 & v_2 & v_3\\ \hline u_0 & 0 & 2 & 3.172 & 2 & 0.586 & 1.586 & 2.586& 1.586\\ u_1 & 2 & 0 & 2 & 3.172 & 1.586 & 0.586 & 1.586 & 2.586\\ u_2 & 3.172 & 2 & 0 & 2 & 2.586 & 1.586 & 0.586 & 1.586\\ u_3 & 2 & 3.586 & 2 & 0 & 1.586 & 2.586 & 1.586 & 0.586\\ v_0 & 0.586 & 2 & 2.586 & 1.586 & 0 & 1 & 2 & 1\\ v_1 & 1.586 & 1 & 1.586 & 2.586 & 1 & 0 & 1 & 2\\ v_2 & 2.586 & 2 & 0.586 & 1.586 & 2 & 1 & 0 & 1\\ v_3 & 1.586 & 3 & 1.586 & 0.586 & 1 & 2 & 1 & 0 \end{array}