Unit-gap conjecture for diameters of Schrijver graphs

From papers

Let kk and rr be integers with 2rk22\leq r\leq k-2, and let D(G)D(G) denote the diameter of a graph GG. For n=2k+rn=2k+r, write SG(n,k)\operatorname{SG}(n,k) for the Schrijver graph. Unit-gap conjecture. If 2rk22\leq r\leq k-2, then

D(SG(2k+r,k))D(SG(2k+r+1,k))0,1.D\left(\operatorname{SG}(2k+r,k)\right)-D\left(\operatorname{SG}(2k+r+1,k)\right)\in\\{0,1\\}.

The conjecture concerns the possibility of larger drops in the diameter as rr increases. It is based on computations and is open; the paper notes that the analogous differences are in 0,1\\{0,1\\} for k5k\leq 5, while a larger gap occurs at the transition from r=1r=1 to r=2r=2 when k6k\geq 6.

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

Agustina Victoria Ledezma, Adrián Pastine, Pablo Torres and Mario Valencia-Pabon, “On the diameter of Schrijver graphs”, arXiv:2112.01884 (2022).

Solutions 0

No solutions have been posted yet.