Near-domination in graphs

Bruce Reed, Alex Scott, Paul Seymour

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 languageEnglish (US)
Pages (from-to)392-407
Number of pages16
JournalJournal of Combinatorial Theory. Series A
StatePublished - Jul 2019

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • Domination
  • Edit distance
  • Threshold graph


Dive into the research topics of 'Near-domination in graphs'. Together they form a unique fingerprint.

Cite this