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.07071
A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. 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. In a previous paper \citeBuiPinUgo20a we proved that every cubical d-polytope is \floord/2-linked. Here we strengthen this result by establishing the \floor(d+1)/2-linkedness of cubical d-polytopes, for every d≠ 3. 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 say that a polytope is (strongly) k-linked if its graph is (strongly) k-linked. In this paper, we also prove that every cubical d-polytope is strongly \floord/2-linked, for every d≠ 3. These results are best possible for this class of polytopes.