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 language | English |
---|---|
Pages (from-to) | 125-135 |
Number of pages | 11 |
Journal | Discrete Mathematics |
Volume | 274 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 6 Jan 2004 |
Externally published | Yes |
Keywords
- Upper domination Ramsey numbers
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics