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

From papers

Let YY be a graph on n2k4n\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,nk,Y)\mathsf{FS}(K_{k,n-k},Y) is the friends-and-strangers graph associated with the graphs Kk,nkK_{k,n-k} and YY. Connectedness conjecture. The graph FS(Kk,nk,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 YCnY\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.

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

Lanchao Wang, Junying Lu and Yaojun Chen, “Connectedness of friends-and-strangers graphs of complete bipartite graphs and others”, arXiv:2302.00900 (2023).

Solutions 0

No solutions have been posted yet.