PDF
Discussiones Mathematicae Graph Theory 26(3) (2006)
419-430
DOI: https://doi.org/10.7151/dmgt.1334
THE UPPER DOMINATION RAMSEY NUMBER u(4,4)
|
Tomasz Dzido
Department of Computer Science |
Renata Zakrzewska
Department of Discrete Mathematics |
Abstract
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.
References
| [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
Close