Connectivity of graphs of polytopes

Seminar/Forum

Room 107
Peter Hall

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, Federation University