The bridge characterization conjecture for double-multiplicity friends-and-strangers graphs

Let XX be a connected simple graph, and let c(X)c^{(X)} and c(Starn)c^{(\mathsf{Star}_n)} be multiplicity lists, with equal total capacity. Let the center of Starn\mathsf{Star}_n have multiplicity

k=c(Starn).k=c^{(\mathsf{Star}_n)}_{\varnothing}.

A kk-bridge is a bridge of the relevant multiplicity determined by the center multiplicity kk. Let FSm,m(X,Starn)\operatorname{\mathsf{FS_{m,m}}}(X,\mathsf{Star}_n) be the double-multiplicity friends-and-strangers graph. The bridge characterization conjecture. The graph FSm,m(X,Starn)\operatorname{\mathsf{FS_{m,m}}}(X,\mathsf{Star}_n) is connected if and only if XX contains no kk-bridge in which all vertices have multiplicity 11. This would extend the paper's connectivity characterizations for single-multiplicity friends-and-strangers graphs to the double-multiplicity setting.

Sources & referencesView supporting material

Primary source

Aleksa Milojevic, “Connectivity of Old and New Models of Friends-and-Strangers Graphs”, arXiv:2210.03864 (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.