View Item 

Connectivity of cubical polytopes

Access Status
Open access
Authors
Bui, Hoa
Pineda-Villavicencio, Guillermo
Ugon, Julien
Date
2020
Type
Journal Article

Metadata
Show full item record
Citation
Bui, H. and Pineda-Villavicencio, G. and Ugon, J. 2020. Connectivity of cubical polytopes. Journal of Combinatorial Theory Series A. 169: Article No. 105126.
Source Title
Journal of Combinatorial Theory Series A
DOI
ISSN
Faculty
Faculty of Science and Engineering
School
School of Electrical Engineering, Computing and Mathematical Sciences (EECMS)
Rights
URI
Collection
Abstract

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.

http://creativecommons.org/licenses/by-nc-nd/4.0/
Except where otherwise noted, this item's license is described as http://creativecommons.org/licenses/by-nc-nd/4.0/