Connectivity of graphs of polytopes


Connectivity of graphs of polytopes

Room 107
Peter Hall
Monash Road


More information

In this talk we explore two questions on the connectivity of graphs of cubical polytopes. A cubical \(d\)-polytope is a polytope with all its facets being combinatorially equivalent to \((d-1)\)-cubes.

Firstly, we establish the following.

(1) For any integer \(d\) at least 3 and any nonnegative integer \(\alpha\) at most \ (d-3\), the graph of a cubical \(d\)-polytope with minimum degree at least \(d+\alpha\) is \((d+\alpha)\)-connected; and

(2) for any integer \(d\) at least 4 and any nonnegative integer \(\alpha\) at most \(d-3\), every separator of cardinality \(d+\alpha\) in such a graph consists of all the neighbours of some vertex and breaks the polytope into exactly two components.

The second question is about the linkedness of cubical polytopes. A graph with at least \(2k\) vertices is \(k\)-linked if, for every set of \(2k\) distinct vertices organised in arbitrary \(k\) pairs of vertices, there are \(k\) vertex-disjoint paths joining the vertices in the pairs. In this direction, the following is our main contribution.

(3) Cubical \(d\)-polytopes are \(\lfloor{(d+1)/2}\rfloor\)-linked for every \(d\) at least 3; this is the maximum possible linkedness for such a class of polytopes.

Other information: This talk will be broadcast online using Zoom conferencing system. Join from PC, Mac, iOS or Android:


  • Dr Guillermo Pineda-Villavicencio
    Dr Guillermo Pineda-Villavicencio, Federation University