- Title
- The linkedness of cubical polytopes : beyond the cube
- Creator
- Bui, Hoa; Pineda-Villavicencio, Guillermo; Ugon, Julien
- Date
- 2024
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/198839
- Identifier
- vital:19100
- Identifier
-
https://doi.org/10.1016/j.disc.2023.113801
- Identifier
- ISSN:0012-365X (ISSN)
- Abstract
- 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 [3] we proved that every cubical d-polytope is ⌊d/2⌋-linked. Here we strengthen this result by establishing the ⌊(d+1)/2⌋-linkedness of cubical d-polytopes, for every d≠3. 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 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 ⌊d/2⌋-linked, for every d≠3. These results are best possible for this class of polytopes.
- Publisher
- Elsevier B.V.
- Relation
- Discrete Mathematics Vol. 347, no. 3 (2024), p.; https://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-nc-nd/4.0/
- Rights
- Copyright © 2023 The Author(s)
- Rights
- Open Access
- Subject
- 4901 Applied mathematics; 4904 Pure mathematics; Connectivity; Cube; Cubical polytope; k-linked; Linkedness; Separator
- Full Text
- Reviewed
- Funder
- Hoa T. Bui is supported by an Australian Government Research Training Program (RTP) Stipend and RTP Fee-Offset Scholarship through Federation University Australia . Julien Ugon's research was partially supported by ARC discovery project DP180100602.
- Hits: 712
- Visitors: 709
- Downloads: 4
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | SOURCE1 | Published version | 708 KB | Adobe Acrobat PDF | View Details Download |