Connectedness conjecture for friends-and-strangers graphs of complete bipartite graphs
Connectedness conjecture for friends-and-strangers graphs of complete bipartite graphs
Let be a graph on vertices. A -bridge is a set of edges whose deletion disconnects the graph, and it is non-trivial when neither resulting component is an isolated vertex. The graph is the friends-and-strangers graph associated with the graphs and . Connectedness conjecture. The graph is connected if and only if is a connected non-bipartite graph without a non-trivial -bridge and . 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
Sign in to submit a solution.
No solutions have been posted yet.