2020/09/12 by Bui, Hoa T., Pineda-Villavicencio, Guillermo, Ugon, Julien
#52B05 #52B12 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2009.07072
The paper is concerned with the linkedness of the graphs of cubical polytopes. A graph with at least 2k vertices is k-linked if, for every set of k disjoint pairs of vertices, there are k vertex-disjoint paths joining the vertices in the pairs. We say that a polytope is k-linked if its graph is k-linked. We establish that the d-dimensional cube is \lfloor(d+1)/2\rfloor-linked, for every d≠ 3; this is the maximum possible linkedness of a d-polytope. This result implies that, for every d≥ 1, a cubical d-polytope is \lfloord/2\rfloor-linked, which answers a question of Wotzlaw \citeRon09. Finally, we introduce the notion of strong linkedness, which is slightly stronger than that of linkedness. A graph G is \it strongly k-linked if it has at least 2k+1 vertices and, for every vertex v of G, the subgraph G-v is k-linked. We show that cubical 4-polytopes are strongly 2-linked and that, for each d≥ 1, d-dimensional cubes are strongly \lfloord/2\rfloor-linked.