Discussiones Mathematicae Graph Theory 26(3) (2006) 419-430
doi: 10.7151/dmgt.1334

[BIBTex] [PDF] [PS]


Tomasz Dzido

Department of Computer Science
University of Gdańsk
Wita Stwosza 57, 80-952 Gdańsk, Poland
e-mail: tdz@math.univ.gda.pl

Renata Zakrzewska

Department of Discrete Mathematics
Gdańsk University of Technology
G. Narutowicza 11/12, 80-952 Gdańsk, Poland
e-mail: renataz@mif.pg.gda.pl


The upper domination Ramsey number u(m,n) is the smallest integer p such that every 2-coloring of the edges of Kp with color red and blue, Γ(B) ≥ m or Γ(R) ≥ n, where B and R is the subgraph of Kp induced by blue and red edges, respectively; Γ(G) is the maximum cardinality of a minimal dominating set of a graph G. In this paper, we show that u(4,4) ≤ 15.

Keywords: edge coloring, upper domination Ramsey number.

2000 Mathematics Subject Classification: 05C15, 05C55, 05C69.


[1] R.C. Brewster, E.J. Cockayne and C.M. Mynhardt, Irredundant Ramsey numbers for graphs, J. Graph Theory 13 (1989) 283-290, doi: 10.1002/jgt.3190130303.
[2] E.J. Cockayne, G. Exoo, J.H. Hattingh and C.M. Mynhardt, The Irredundant Ramsey Number s(4,4), Util. Math. 41 (1992) 119-128.
[3] E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977) 247-261, doi: 10.1002/net.3230070305.
[4] R.E. Greenwood and A.M. Gleason, Combinatorial relations and chromatic graphs, Canadian J. Math. 7 (1955) 1-7, doi: 10.4153/CJM-1955-001-4.
[5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of domination in graphs, Marcel Dekker, New York, (1998) (Proposition 3.8, p. 72).
[6] M.A. Henning and O.R. Oellermann, The upper domination Ramsey number u(3,3,3), Discrete Math. 242 (2002) 103-113, doi: 10.1016/S0012-365X(00)00369-1.
[7] M.A. Henning and O.R. Oellermann, On upper domination Ramsey numbers for graphs, Discrete Math. 274 (2004) 125-135, doi: 10.1016/S0012-365X(03)00084-0.

Received 11 October 2005
Revised 4 July 2006