Monotonicity conjecture for the diameter of Schrijver graphs

About 5 years old · traced to

Let kk and rr be integers with r≥1r\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 r≥1r\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 r≤2r\leq 2 and when r≥k−3r\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.

References

Primary source

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

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.