The linkedness of cubical polytopes: The cube
| Autor: | Hoa T. Bui, Julien Ugon, Guillermo Pineda Villavicencio |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Mathematics::Combinatorics
Applied Mathematics 52B05 52B12 Cube (algebra) Polytope Theoretical Computer Science Combinatorics Computational Theory and Mathematics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Geometry and Topology Combinatorics (math.CO) Mathematics |
| DOI: | 10.48550/arxiv.2009.07072 |
| Popis: | The paper is concerned with the linkedness of the graphs of cubical polytopes. A graph with at least $2k$ vertices is \textit{$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 \textit{$k$-linked} if its graph is $k$-linked. We establish that the $d$-dimensional cube is $\floor{(d+1)/2}$-linked, for every $d\ne 3$; this is the maximum possible linkedness of a $d$-polytope. This result implies that, for every $d\ge 1$, a cubical $d$-polytope is $\floor{d/2}$-linked, which answers a question of Wotzlaw \cite{Ron09}. 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\ge 1$, $d$-dimensional cubes are strongly $\floor{d/2}$-linked. Comment: 20 pages,4 figures. arXiv admin note: text overlap with arXiv:1802.09230 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|