- Title
- The linkedness of cubical polytopes: the cube
- Creator
- Bui, Hoa; Pineda-Villavicencio, Guillermo; Ugon, Julien
- Date
- 2021
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/179082
- Identifier
- vital:15492
- Identifier
-
https://doi.org/10.37236/9848
- Identifier
- ISBN:1077-8926 (ISSN)
- Abstract
- 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 [(d + 1)/2]-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 [d/2]-linked, which answers a question of Wotzlaw (Incidence graphs and unneighborly polytopes, Ph.D. thesis, 2009). Finally, we introduce the notion of strong linkedness, which is slightly stronger than that of linkedness. A graph G is 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
- Publisher
- Australian National University
- Relation
- Electronic Journal of Combinatorics Vol. 28, no. 3 (2021), p.; http://purl.org/au-research/grants/arc/DP180100602
- Rights
- All metadata describing materials held in, or linked to, the repository is freely available under a CC0 licence
- Rights
- http://creativecommons.org/licenses/by-nd/4.0/
- Rights
- Copyright © The authors
- Rights
- Open Access
- Subject
- 0101 Pure Mathematics; 0802 Computation Theory and Mathematics
- Full Text
- Reviewed
- Funder
- Julien Ugon’s research was partially supported by ARC discovery project DP180100602.
- Hits: 650
- Visitors: 666
- Downloads: 62
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | SOURCE1 | Published version | 978 KB | Adobe Acrobat PDF | View Details Download |