# On 1-dependent ramsey numbers for graphs

Discussiones Mathematicae Graph Theory (1999)

- Volume: 19, Issue: 1, page 93-110
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topE.J. Cockayne, and C.M. Mynhardt. "On 1-dependent ramsey numbers for graphs." Discussiones Mathematicae Graph Theory 19.1 (1999): 93-110. <http://eudml.org/doc/270631>.

@article{E1999,

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 t₁(l,m) is the smallest integer n such that for any 2-edge colouring (R,B) of Kₙ, the spanning subgraph B of Kₙ 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 t₁(l,m) Ramsey colouring of Kₙ 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 t₁(4,5) = 9, t₁(4,6) = 11, t₁(4,7) = 16 and t₁(4,8) = 17. We also determine all (4,4,5), (4,5,8), (4,6,10) and (4,7,15) Ramsey graphs.},

author = {E.J. Cockayne, C.M. Mynhardt},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {1-dependence; irredundance; CO-irredundance; Ramsey numbers; Ramsey number; 1-dependent set; Ramsey colouring; Ramsey graph},

language = {eng},

number = {1},

pages = {93-110},

title = {On 1-dependent ramsey numbers for graphs},

url = {http://eudml.org/doc/270631},

volume = {19},

year = {1999},

}

TY - JOUR

AU - E.J. Cockayne

AU - C.M. Mynhardt

TI - On 1-dependent ramsey numbers for graphs

JO - Discussiones Mathematicae Graph Theory

PY - 1999

VL - 19

IS - 1

SP - 93

EP - 110

AB - 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 t₁(l,m) is the smallest integer n such that for any 2-edge colouring (R,B) of Kₙ, the spanning subgraph B of Kₙ 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 t₁(l,m) Ramsey colouring of Kₙ 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 t₁(4,5) = 9, t₁(4,6) = 11, t₁(4,7) = 16 and t₁(4,8) = 17. We also determine all (4,4,5), (4,5,8), (4,6,10) and (4,7,15) Ramsey graphs.

LA - eng

KW - 1-dependence; irredundance; CO-irredundance; Ramsey numbers; Ramsey number; 1-dependent set; Ramsey colouring; Ramsey graph

UR - http://eudml.org/doc/270631

ER -

## References

top- [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. Zbl0686.05038
- [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. Zbl0952.05051
- [4] E.J. Cockayne, G. MacGillivray and J. Simmons, CO-irredundant Ramsey numbers for graphs, submitted. Zbl0958.05092
- [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). Zbl0890.05002
- [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. Zbl0982.05068
- [9] G. MacGillivray, personal communication, 1998.
- [10] C.M. Mynhardt, Irredundant Ramsey numbers for graphs: a survey, Congr. Numer. 86 (1992) 65-79. Zbl0783.05075
- [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. Zbl55.0032.04
- [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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.