The diameter of the generalized Petersen graph $GP[tk,k]$

Gulnaz Boruzanli
Ege University

John Baptist Gauci
University of Malta



Content: For integers $n\geq 3$ and $ 1\leq k < n $, the generalized Petersen graph $GP[n,k]$ has $2n$ vertices $\{u_0, u_1, \ldots, u_{n-1}, v_0, v_1, \ldots, v_{n-1}\}$ and $3n$ edges $\allowbreak\{u_iu_{i+1}, v_iv_{i+k}, u_iv_i | i=0, 1, \ldots, n-1; \textrm{addition} \bmod{n}\}$. We investigate the diameter, that is the maximum length of the shortest path between any two vertices, of this family of graphs, where $ n=tk $ for any integer $ t\geq 2 $. The diameter is an important invariant in interconnection networks, and diameter problems are often encountered in network optimization. Most of the well--known networks have small girth, and, consequently, generalized Petersen graphs are good candidates for such networks since their girth is at most eight. The diameter of $GP[n,1]$ for $n\geq 3$ is trivially $\lfloor\frac{n}{2}\rfloor +1$. We show that the diameter of $GP[tk,k]$ for $k\geq 2$ and $t\geq 2$ is $\lfloor\frac{t+k+3}{2}\rfloor$.

Back to all abstracts