The eventual non-ℓ\ell-distance-balance conjecture for generalized Petersen graphs

About 9 years old · traced to

Let GP(n,k)GP(n,k) be the generalized Petersen graph, let dd denote graph distance, and let DD be its diameter. For an integer k≥2k\geq 2, define

nk={11,k=2,(k+1)2,k odd,k(k+2),k≥4 even.n_k=\begin{cases}11,&k=2,\\(k+1)^2,&k\text{ odd},\\k(k+2),&k\geq4\text{ even}. \end{cases}

The eventual non-ℓ\ell-distance-balance conjecture. For any n>nkn>n_k, the graph GP(n,k)GP(n,k) is not ℓ\ell-distance-balanced for any integer ℓ\ell with 1≤ℓ<D1\leq\ell<D. Moreover, nkn_k is the smallest integer with this property. The conjecture formalizes computational evidence that, for each fixed kk, sufficiently large generalized Petersen graphs are diameter-distance-balanced but fail to be ℓ\ell-distance-balanced at every smaller distance.

References

Primary source

Stefko Miklavic and Primoz Sparl, “-distance-balanced graphs”, arXiv:1702.05257 (2017).

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.