Toughness and Delaunay triangulations

摘要

We show that nondegenerate Delaunay triangulations satisfy a combinatorial property called 1-toughness. A graph with set of sites S is 1-tough if for any set P ⊆ S, c(S - P) ≤ |S|, where c(S - P) is the number of components of the subgraph induced by the complement of P and |P| is the number of sites in P. We also show that, under the same conditions, the number of interior components of S - P is at most |P| - 2. These appear to be the first nontrivial properties of a purely combinatorial nature to be established for Delaunay triangulations. We give examples to show that these bounds can be attained, and we state and prove several corollaries. In particular, we show that maximal planar graphs inscribable in a sphereare 1-tough.