On the Graph Connectivity of Skeleta of Convex Polytopes
On the Graph Connectivity of Skeleta of Convex Polytopes
复制标题
凸多面体骨架的图连通性
DOI：
--
复制
发表时间：
2008
影响因子：
0.8
通讯作者：
Christos A. Athanasiadis
中科院分区：
文献类型：
--
作者：
Christos A. Athanasiadis
给定一个d维凸多面体P和不超过d−1的非负整数k，设
${mathcal{G}}_{k}（P）$
表示P的k维面的节点集上的简单图，其中两个这样的面相邻，如果存在P的（k+1）维面，其中包含它们。图形
${mathcal{G}}_{k}（P）$
同构于P的正规扇的（d-k）维骨架的对偶图。对于k和d的固定值，最大整数m使得
${mathcal{G}}_{k}（P）$
是m-顶点连通的。这个结果推广了Balinski关于d维凸多面体的一维骨架的定理。
AbstractGiven a d-dimensional convex polytope P and nonnegative integer k not exceeding d−1, let
${mathcal{G}}_{k}(P)$
denote the simple graph on the node set of k-dimensional faces of P in which two such faces are adjacent if there exists a (k+1)-dimensional face of P which contains them both. The graph
${mathcal{G}}_{k}(P)$
is isomorphic to the dual graph of the (d−k)-dimensional skeleton of the normal fan of P. For fixed values of k and d, the largest integer m such that
${mathcal{G}}_{k}(P)$
is m-vertex-connected for all d-dimensional polytopes P is determined. This result generalizes Balinski’s theorem on the one-dimensional skeleton of a d-dimensional convex polytope.