Diameter formula for generalized Petersen graphs

From papers

Let GPG(n,s)GPG(n,s) be the generalized Petersen graph and let Cn(1,s)C_n(1,s) be the circulant graph with step sizes 11 and ss. Let n5n\geq 5 and 2sn122\leq s\leq \lfloor \frac{n-1}{2} \rfloor. Diameter formula. We have

D(GPG(n,s))={D(Cn(1,s))+1if n=4p and s=2p1 with p>2,D(Cn(1,s))+2otherwise.D(GPG(n,s)) = \begin{cases} D(C_n(1,s)) + 1 & \text{if } n=4p \text{ and } s=2p-1 \text{ with } p>2,\\ D(C_n(1,s)) + 2 & \text{otherwise.} \end{cases}

This gives an exact relation between the diameters of generalized Petersen graphs and the corresponding circulant graphs; together with the preceding diameter bounds for Cn(1,s)C_n(1,s), it yields explicit upper bounds for GPG(n,s)GPG(n,s).

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Laila Loudiki, Mustapha Kchikech and El Hassan Essaky, “Diameter of generalized Petersen graphs”, arXiv:2102.10397 (2023).

Additional references

2 papers in this index state this conjecture (2019–2021). The statement above is taken from the most recent of them; the others are arXiv:1901.11156.

Solutions 0

No solutions have been posted yet.