Near-domination in graphs

Author: 

Reed, B
Scott, A
Seymour, P

Publication Date: 

July 2019

Journal: 

JOURNAL OF COMBINATORIAL THEORY SERIES A

Last Updated: 

2019-08-17T17:36:13.393+01:00

Volume: 

165

DOI: 

10.1016/j.jcta.2019.02.009

page: 

392-407

abstract: 

© 2019 Elsevier Inc. 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.

Symplectic id: 

983162

Download URL: 

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article