The cycle-barbell-theta girth conjecture for star friends-and-strangers graphs

Let XX be a connected graph with finite girth, let C\mathcal C be the set of cycle subgraphs of FS(X,Starn)\mathsf{FS}(X,\textsf{Star}_n) that achieve its girth, and for each CCC\in\mathcal C let XCX_C be the path-induced subgraph of XX by CC. Set

X={XC}CC.\mathcal X=\{X_C\}_{C\in\mathcal C}.

The cycle-barbell-theta girth conjecture asserts that some XCXX_C\in\mathcal X is isomorphic to a cycle, barbell, or theta graph, and that the girth can be computed by taking the corresponding sequence of swaps around that graph. The statement is a proposed structural characterization of shortest cycles in these friends-and-strangers graphs; the supplied text gives no resolution.

Sources & referencesView supporting material

Primary source

Ryan Jeong, “On the Diameters of Friends-and-Strangers Graphs”, arXiv:2201.00665 (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.