On linkages in polytope graphs
Axel Werner, Ronald F. Wotzlaw · Advances in Geometry · 2011
Abstract A graph is k-linked if any k disjoint vertex-pairs can be joined by k disjoint paths. We slightly improve a lower bound on the linkedness of polytopes. This results in exact values for the minimal linkedness of 7-, 10- and 13-dimensional polytopes. We analyze in detail linkedness of d-polytopes on at most (6d + 7)/5 vertices. In that case, a tight lower bound on minimal linkedness is derived, and examples meeting this lower bound are constructed. These examples contain a class of examples due to Gallivan.