ArticleOriginal scientific text
Title
The upper domination Ramsey number u(4,4)
Authors 1, 2
Affiliations
- Department of Computer Science, University of Gdańsk, Wita Stwosza 57, 80-952 Gdańsk, Poland
- Department of Discrete Mathematics, Gdańsk University of Technology, G. Narutowicza 11/12, 80-952 Gdańsk, Poland
Abstract
The upper domination Ramsey number u(m,n) is the smallest integer p such that every 2-coloring of the edges of Kₚ with color red and blue, Γ(B) ≥ m or Γ(R) ≥ n, where B and R is the subgraph of Kₚ 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
Bibliography
- 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.
- 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.
- E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977) 247-261, doi: 10.1002/net.3230070305.
- 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.
- 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).
- 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.
- 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.
Pages:
419-430
Main language of publication
English
Received
2005-10-11
Accepted
2006-07-04
Published
2006
DOI: 10.7151/dmgt.1334
Exact and natural sciences