The disjoint-path connectivity conjecture for friends-and-strangers graphs with a star

Let XX be a graph on nn vertices, and let \Starn\Star_n denote the star graph on nn vertices. Write

G=FS(X,\Starn),G=\operatorname{FS}(X,\Star_n),

and assume that GG is connected. For permutations σ\sigma and ρ\rho in V(G)V(G), the maximum number of disjoint paths between σ\sigma and ρ\rho is

min{deg(σ),deg(ρ)}.\min\{\deg(\sigma),\deg(\rho)\}.

Disjoint-path connectivity conjecture. The maximum number of disjoint paths between any two permutations σ\sigma and ρ\rho in GG equals min{deg(σ),deg(ρ)}\min\{\deg(\sigma),\deg(\rho)\}. This would determine the local vertex connectivity between every pair of vertices in this class of friends-and-strangers graphs, extending the paper's connectivity results and the evidence provided by starcle graphs. The conjecture is presented as a future research direction, and its resolution is not given here.

Sources & referencesView supporting material

Primary source

Neil Krishnan and Rupert Li, “On the Connectivity of Friends-and-strangers Graphs”, arXiv:2410.21334 (2024).

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.