Connectivity of graphs of polytopes

Seminar/Forum

Connectivity of graphs of polytopes

Room 107
Peter Hall
Monash Road

Map

More information

sanming@unimelb.edu.au

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: https://unimelb.zoom.us/j/931478513

Presenter

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