The diameter of the generalized Petersen graph $GP[n,m]$ for coprime integers $n$ and $m$

John Baptist Gauci
University of Malta

Gulnaz Boruzanli
Ege University



Content: The problem of calculating the distances among all pairs of vertices in a graph has been studied for a long time. The diameter of a graph is found by identifying the pair of vertices which are the furthest apart. In this work, we investigate the diameter of the family of generalized Petersen graphs $GP[n,m]$ where $n$ and $m$ are coprime positive integers. The graph $GP[n,m]$ is the graph on the $2n$ vertices $\{u_0, u_1, \ldots, u_{n-1}, v_0, v_1, \ldots, v_{n-1}\}$ having $3n$ edges $\{u_iu_{i+1}, v_iv_{i+m}, u_iv_i | i=0,\ldots, n-1; \textrm{addition} \bmod{n}\}$. Zhang \textit{et al.} [1] showed that the diameter of the generalized Petersen graphs is of the order $O(\frac{n}{2m})$. We show that, for coprime positive integers $n$ and $m$, the diameter of $GP[n,m]$ depends on the parity of $\lfloor\frac{n}{m}\rfloor$ and on the value of $n\bmod{m}$, and establish exact values for the diameter of this family of graphs. \vspace{5mm} \noindent\textbf{References:} \begin{itemize} \item[{[1]}] J. Zhang, X.-R. Xu, \& J. Wang. Wide Diameter of Generalized Petersen Graphs. \emph{Journal of Mathematical Research \& Exposition}, 30(3): 562--566, 2010. \end{itemize}

Back to all abstracts