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

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 k2k\geq 2, define

nk={11,k=2,(k+1)2,k odd,\k(k+2),k4 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.

Sources & referencesView supporting material

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.