The biconnected friends-and-strangers connectivity conjecture

About 4 years old · traced to

Let YY be a graph on n≥3n\geq 3 vertices such that its complement is a forest consisting of trees T1,…,Tr\mathcal T_1,\dots,\mathcal T_r with

gcd⁡(∣V(T1)∣,…,∣V(Tr)∣)=1.\gcd\bigl(|V(\mathcal T_1)|,\dots,|V(\mathcal T_r)|\bigr)=1.

If XX is a biconnected graph on nn vertices, the biconnected connectivity conjecture asserts that FS(X,Y)\mathsf{FS}(X,Y) is connected. This generalizes the known characterization for X=CyclenX=\textsf{Cycle}_n to all biconnected graphs and is attributed in the source to Defant et al.; it remains open in the supplied text.

References

Primary source

Ryan Jeong, “On the Diameters of Friends-and-Strangers Graphs”, arXiv:2201.00665 (2023).

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.