On upper domination Ramsey numbers for graphs

Michael A. Henning, Ortrud R. Oellermann

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

The classical Ramsey number r(m,n) can be defined as the smallest integer p such that in every two-coloring (R,B) of the edges of Kp, β(B) ≥ m or β(R) ≥ n, where β(G) denotes the independence number of a graph G. We define the upper domination Ramsey number u(m,n) as the smallest integer p such that in every two-coloring (R,B) of the edges of Kp, Γ(B) ≥ m or Γ(R) ≥ n, where Γ(G) is the maximum cardinality of a minimal dominating set of a graph G. The mixed domination Ramsey number v(m,n) is defined to be the smallest integer p such that in every two-coloring (R,B) of the edges of Kp, Γ(B) ≥ m or β(R) ≥ n. Since β(G) ≤ Γ(G) for every graph G, u(m,n) ≤ v(m,n) ≤ r(m,n). We develop techniques to obtain upper bounds for upper domination Ramsey numbers of the form u(3,n) and mixed domination Ramsey numbers of the form v(3,n). We show that u(3,3)=v(3,3)=6, u(3,4)=8, v(3,4)=9, u(3,5)=v(3,5)=12 and u(3,6)=v(3,6)=15.

Original languageEnglish
Pages (from-to)125-135
Number of pages11
JournalDiscrete Mathematics
Volume274
Issue number1-3
DOIs
Publication statusPublished - 6 Jan 2004
Externally publishedYes

Keywords

  • Upper domination Ramsey numbers

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On upper domination Ramsey numbers for graphs'. Together they form a unique fingerprint.

Cite this