Near-domination in graphs

<p>A vertex <em>u</em> of a graph “<em>t</em>-dominates” a vertex <em>v</em> if there are at most <em>t</em> vertices different from <em>u</em>,<em> v</em> that are adjacent to <em>v</em> and not to <em>u</em>; and a graph is “<em>t</em>-dominating” if for every pair of distinct vertices, one of them <em>t</em>-dominates the other. Our main result says that if a graph is <em>t</em>-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 Erdős-Hajnal conjecture.</p>