  A vertex u of a graph t-dominates a vertex v if there are at most t vertices
different from u,v that are adjacent to v and not to u; and a graph is
t-dominating if for every pair of distinct vertices, one of them t-dominates
the other. Our main result says that if a graph is t-dominating, then it is
close (in an appropriate sense) to being 0-dominating. We also show that an
analogous statement for digraphs is false; and discuss some connections with
the Erdos-Hajnal conjecture.

Combinatorics