Abstract
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 Erdős-Hajnal conjecture.
Original language | English (US) |
---|---|
Pages (from-to) | 392-407 |
Number of pages | 16 |
Journal | Journal of Combinatorial Theory. Series A |
Volume | 165 |
DOIs | |
State | Published - Jul 2019 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Keywords
- Domination
- Edit distance
- Threshold graph