Diameter formula for generalized Petersen graphs

About 7 years old · traced to

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 n≥5n\geq 5 and 2≤s≤⌊n−12⌋2\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=2p−1 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).

References

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.

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.