The quadratic diameter conjecture for friends-and-strangers graphs on cycles
The quadratic diameter conjecture for friends-and-strangers graphs on cycles
From papers
Let be a graph on vertices, and let denote its friends-and-strangers graph. The quadratic diameter conjecture asserts that the maximum diameter of a connected component of
is . This would sharpen the paper's polynomial diameter bound for cycles; the conjecture is presented as an unresolved improvement, and would imply an bound for the corresponding double-flip distances.
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
Ryan Jeong, “On the Diameters of Friends-and-Strangers Graphs”, arXiv:2201.00665 (2023).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.