2007/10/19 by Axel Werner, Werner, Axel, Ronald F. Wotzlaw +1
Mathematics · #05C38 #52B05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C38 #msc:52B05
paper · pdf · doi:10.48550/arxiv.0710.3726
14 pages, 4 figures
arxiv created 2007/10/19 · arxiv updated 2009/12/01
A graph is k-linked if any k disjoint vertex-pairs can be joined by k disjoint paths. We improve a lower bound on the linkedness of polytopes slightly, which results in exact values for the minimal linkedness of 7-, 10- and 13-dimensional polytopes. We analyze in detail linkedness of polytopes on at most (6d+7)/5 vertices. In that case, a sharp 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.