## 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 K_{p}, β(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 K_{p}, Γ(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 K_{p}, Γ(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