The cycle-barbell-theta girth conjecture for star friends-and-strangers graphs
The cycle-barbell-theta girth conjecture for star friends-and-strangers graphs
Let be a connected graph with finite girth, let be the set of cycle subgraphs of that achieve its girth, and for each let be the path-induced subgraph of by . Set
The cycle-barbell-theta girth conjecture asserts that some 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.