The linkedness characterization of the two-agent price of connectivity
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.