The linkedness characterization of the two-agent price of connectivity
Let be a biconnected graph. For positive integers , say that is -linked if, for every pair of disjoint vertex sets with and , there are disjoint connected subgraphs such that for . Let denote the price of connectivity for two agents. Linkedness conjecture. If is an integer and is -linked but not -linked, then
The conjecture would determine the price of connectivity for the two-agent case in terms of linkedness; the paper verifies it for complete graphs with an arbitrary matching removed, but does not establish it for general biconnected graphs.
References
Primary source
Xiaohui Bei, Ayumi Igarashi, Xinhang Lu and Warut Suksompong, “The Price of Connectivity in Fair Division”, arXiv:1908.05433 (2022).
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
No solutions have been posted yet.