Connectedness conjecture for friends-and-strangers graphs of complete bipartite graphs

At least 2 years old · documented by

Let YY be a graph on n≥2k≥4n\ge 2k\ge 4 vertices. A kk-bridge is a set of kk edges whose deletion disconnects the graph, and it is non-trivial when neither resulting component is an isolated vertex. The graph FS(Kk,n−k,Y)\mathsf{FS}(K_{k,n-k},Y) is the friends-and-strangers graph associated with the graphs Kk,n−kK_{k,n-k} and YY. Connectedness conjecture. The graph FS(Kk,n−k,Y)\mathsf{FS}(K_{k,n-k},Y) is connected if and only if YY is a connected non-bipartite graph without a non-trivial kk-bridge and Y≠CnY\not=C_n. This conjecture extends the established disconnectedness criterion, while the cited theorems provide only weaker sufficient conditions for connectedness; the full characterization remains open.

References

Primary source

Lanchao Wang, Junying Lu and Yaojun Chen, “Connectedness of friends-and-strangers graphs of complete bipartite graphs and others”, arXiv:2302.00900 (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.