Near-domination in graphs

Bruce Reed; Alex Scott; Paul Seymour

doi:10.1016/j.jcta.2019.02.009

Near-domination in graphs

Bruce Reed, Alex Scott, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

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	https://doi.org/10.1016/j.jcta.2019.02.009
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

Access to Document

10.1016/j.jcta.2019.02.009

Cite this

@article{2f8e99c645f7422787cd86862f82421c,

title = "Near-domination in graphs",

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{\H o}s-Hajnal conjecture.",

keywords = "Domination, Edit distance, Threshold graph",

author = "Bruce Reed and Alex Scott and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier Inc.",

year = "2019",

month = jul,

doi = "10.1016/j.jcta.2019.02.009",

language = "English (US)",

volume = "165",

pages = "392--407",

journal = "Journal of Combinatorial Theory. Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Near-domination in graphs

AU - Reed, Bruce

AU - Scott, Alex

AU - Seymour, Paul

PY - 2019/7

Y1 - 2019/7

N2 - 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.

AB - 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.

KW - Domination

KW - Edit distance

KW - Threshold graph

UR - http://www.scopus.com/inward/record.url?scp=85062803007&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85062803007&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2019.02.009

DO - 10.1016/j.jcta.2019.02.009

M3 - Article

AN - SCOPUS:85062803007

SN - 0097-3165

VL - 165

SP - 392

EP - 407

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

ER -

Near-domination in graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this