The linkedness of cubical polytopes

MaRDI QIDQ6298235zbMATH OpenFDO

Authors Hoa Thi Bui, Guillermo Pineda-Villavicencio, Julien Ugon

Publication date 26 February 2018

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Abstract: A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. The paper is concerned with the linkedness of the graphs 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. Larman and Mani in 1970 proved that simplicial $d$-polytopes, polytopes with all their facets being combinatorially equivalent to simplices, are $floor(d+1)/2$-linked; this is the maximum possible linkedness given the facts that a $floor(d+1)/2$-linked graph is at least $(2floor(d+1)/2-1)$-connected and that some of these graphs are $d$-connected but not $(d+1)$-connected. Here we establish that cubical $d$-polytopes are also $floor(d+1)/2$-linked for every $de3$; this is again the maximum possible linkedness for such a class of polytopes.

This page was built for publication: The linkedness of cubical polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6298235)