The disjoint-path connectivity conjecture for friends-and-strangers graphs with a star
The disjoint-path connectivity conjecture for friends-and-strangers graphs with a star
Let be a graph on vertices, and let denote the star graph on vertices. Write
and assume that is connected. For permutations and in , the maximum number of disjoint paths between and is
Disjoint-path connectivity conjecture. The maximum number of disjoint paths between any two permutations and in equals . 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
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.