Connectivity of cubical polytopes
A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. We deal with the connectivity of the graphs of cubical polytopes. We first establish that, for any d≥3, the graph of a cubical d-polytope with minimum degree δ is min{δ,2d−2}-connected. Second, we show,...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Language: | English |
| Published: |
Elsevier
2020
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/81335 |
| _version_ | 1848764349512941568 |
|---|---|
| author | Bui, Hoa Pineda-Villavicencio, Guillermo Ugon, Julien |
| author_facet | Bui, Hoa Pineda-Villavicencio, Guillermo Ugon, Julien |
| author_sort | Bui, Hoa |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. We deal with the connectivity of the graphs of cubical polytopes. We first establish that, for any d≥3, the graph of a cubical d-polytope with minimum degree δ is min{δ,2d−2}-connected. Second, we show, for any d≥4, that every minimum separator of cardinality at most 2d−3 in such a graph consists of all the neighbours of some vertex and that removing the vertices of the separator from the graph leaves exactly two components, with one of them being the vertex itself. |
| first_indexed | 2025-11-14T11:17:57Z |
| format | Journal Article |
| id | curtin-20.500.11937-81335 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T11:17:57Z |
| publishDate | 2020 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-813352021-08-12T07:59:34Z Connectivity of cubical polytopes Bui, Hoa Pineda-Villavicencio, Guillermo Ugon, Julien 0102 - Applied Mathematics 0103 - Numerical and Computational Mathematics 0101 - Pure Mathematics A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. We deal with the connectivity of the graphs of cubical polytopes. We first establish that, for any d≥3, the graph of a cubical d-polytope with minimum degree δ is min{δ,2d−2}-connected. Second, we show, for any d≥4, that every minimum separator of cardinality at most 2d−3 in such a graph consists of all the neighbours of some vertex and that removing the vertices of the separator from the graph leaves exactly two components, with one of them being the vertex itself. 2020 Journal Article http://hdl.handle.net/20.500.11937/81335 10.1016/j.jcta.2019.105126 English http://creativecommons.org/licenses/by-nc-nd/4.0/ Elsevier fulltext |
| spellingShingle | 0102 - Applied Mathematics 0103 - Numerical and Computational Mathematics 0101 - Pure Mathematics Bui, Hoa Pineda-Villavicencio, Guillermo Ugon, Julien Connectivity of cubical polytopes |
| title | Connectivity of cubical polytopes |
| title_full | Connectivity of cubical polytopes |
| title_fullStr | Connectivity of cubical polytopes |
| title_full_unstemmed | Connectivity of cubical polytopes |
| title_short | Connectivity of cubical polytopes |
| title_sort | connectivity of cubical polytopes |
| topic | 0102 - Applied Mathematics 0103 - Numerical and Computational Mathematics 0101 - Pure Mathematics |
| url | http://hdl.handle.net/20.500.11937/81335 |