Edge connectivity of simplicial polytopes
2021
A simplicial polytope is a polytope with all its facets being combinatorially
equivalent to simplices. We deal with the edge connectivity of the graphs of
simplicial polytopes. We first establish that, for any $d\ge 3$, for any $d\ge
3$, every minimum edge cut of cardinality at most $4d-7$ in such a graph is
\textit{trivial}, namely it consists of all the edges incident with some
vertex. A consequence of this is that, for $d\ge 3$, the graph of a simplicial
$d$-polytope with minimum degree $\delta$ is
$\min\{\delta,4d-6\}$-edge-connected. In the particular case of $d=3$, we have
that every minimum edge cut in a plane triangulation is trivial; this may be of
interest to researchers in graph theory. Second, for every $d\ge 4$ we construct a simplicial $d$-polytope whose graph
has a nontrivial minimum edge cut of cardinality $(d^{2}+d)/2$. This gives a
simplicial 4-polytope with a nontrivial minimum edge cut that has ten edges.
Thus, the aforementioned result is best possible for simplicial $4$-polytopes.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
10
References
0
Citations
NaN
KQI