DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 19(1) (1999) 93-110
DOI: 10.7151/dmgt.1088

ON 1-DEPENDENT RAMSEY NUMBERS FOR GRAPHS

E.J. Cockayne

Department of Mathematics, University of Victoria
P.O. Box 3045, Victoria, BC, CANADA V8W 3P4

C.M. Mynhardt

Department of Mathematics, University of South Africa
P.O. Box 392, Pretoria, South Africa 0003

Abstract

A set X of vertices of a graph G is said to be 1-dependent if the subgraph of G induced by X has maximum degree one. The 1-dependent Ramsey number t1(l,m) is the smallest integer n such that for any 2-edge colouring (R,B) of Kn, the spanning subgraph B of Kn has a 1-dependent set of size l or the subgraph R has a 1-dependent set of size m. The 2-edge colouring (R,B) is a t1(l,m) Ramsey colouring of Kn if B (R, respectively) does not contain a 1-dependent set of size l (m, respectively); in this case R is also called a (l,m,n) Ramsey graph. We show that t1(4,5) = 9, t1(4,6) = 11, t1(4,7) = 16 and t1(4,8) = 17. We also determine all (4,4,5), (4,5,8), (4,6,10) and (4,7,15) Ramsey graphs.

Keywords: 1-dependence, irredundance, CO-irredundance, Ramsey numbers.

1991 Mathematics Subject Classification: 05C55, 05C70.

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] G. Chartrand and L. Lesniak, Graphs and Digraphs (Third Edition) (Chapman and Hall, London, 1996).
[3] E.J. Cockayne, Generalized irredundance in graphs: Hereditary properties and Ramsey numbers, submitted.
[4] E.J. Cockayne, G. MacGillivray and J. Simmons, CO-irredundant Ramsey numbers for graphs, submitted.
[5] E.J. Cockayne, C.M. Mynhardt and J. Simmons, The CO-irredundant Ramsey number t(4,7), submitted.
[6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
[7] H. Harborth and I Mengersen, All Ramsey numbers for five vertices and seven or eight edges, Discrete Math. 73 (1988/89) 91-98, doi: 10.1016/0012-365X(88)90136-7.
[8] C.J. Jayawardene and C.C. Rousseau, The Ramsey numbers for a quadrilateral versus all graphs on six vertices, to appear.
[9] G. MacGillivray, personal communication, 1998.
[10] C.M. Mynhardt, Irredundant Ramsey numbers for graphs: a survey, Congr. Numer. 86 (1992) 65-79.
[11] S.P. Radziszowski, Small Ramsey numbers, Electronic J. Comb. 1 (1994) DS1.
[12] F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (1930) 264-286, doi: 10.1112/plms/s2-30.1.264.
[13] J. Simmons, CO-irredundant Ramsey numbers for graphs, Master's dissertation, University of Victoria, Canada, 1998.
[14] Zhou Huai Lu, The Ramsey number of an odd cycle with respect to a wheel, J. Math. - Wuhan 15 (1995) 119-120.

Received 14 July 1998
Revised 12 April 1999