Monotonicity conjecture for the diameter of Schrijver graphs

From papers

Let kk and rr be integers with r1r\geq 1, 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. Monotonicity conjecture. If r1r\geq 1, then

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

The authors have determined the exact diameter when r2r\leq 2 and when rk3r\geq k-3, and provide bounds in the remaining range. Their computations suggest that the diameter is non-increasing as rr increases, but the conjecture remains open.

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.