The linkedness of cubical polytopes: the cube (Q2049620)

Summary: The paper is concerned with the linkedness of the graphs of cubical polytopes. A graph with at least \(2k\) vertices is \(k\)-\textit{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\ne 3\); this is the maximum possible linkedness of a \(d\)-polytope. This result implies that, for every \(d\geqslant 1\), a cubical \(d\)-polytope is \(\lfloor d/2\rfloor \)-linked, which answers a question of \textit{R. F. Wotzlaw} [Incidence graphs and unneighborly polytopes. Berlin: TU Berlin, Fakultät II, Mathematik und Naturwissenschaften (Diss.) (2009; Zbl 1233.52003)]. Finally, we introduce the notion of strong linkedness, which is slightly stronger than that of linkedness. A graph \(G\) is \textit{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\geqslant 1, d\)-dimensional cubes are strongly \(\lfloor d/2\rfloor\)-linked.