On 1-dependent ramsey numbers for graphs

E.J. Cockayne; C.M. Mynhardt

Discussiones Mathematicae Graph Theory (1999)

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

Abstract

top
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.

How to cite

top

E.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. [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. [2] G. Chartrand and L. Lesniak, Graphs and Digraphs (Third Edition) (Chapman and Hall, London, 1996). 
  3. [3] E.J. Cockayne, Generalized irredundance in graphs: Hereditary properties and Ramsey numbers, submitted. Zbl0952.05051
  4. [4] E.J. Cockayne, G. MacGillivray and J. Simmons, CO-irredundant Ramsey numbers for graphs, submitted. Zbl0958.05092
  5. [5] E.J. Cockayne, C.M. Mynhardt and J. Simmons, The CO-irredundant Ramsey number t(4,7), submitted. 
  6. [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  7. [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. [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. [9] G. MacGillivray, personal communication, 1998. 
  10. [10] C.M. Mynhardt, Irredundant Ramsey numbers for graphs: a survey, Congr. Numer. 86 (1992) 65-79. Zbl0783.05075
  11. [11] S.P. Radziszowski, Small Ramsey numbers, Electronic J. Comb. 1 (1994) DS1. 
  12. [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. [13] J. Simmons, CO-irredundant Ramsey numbers for graphs, Master's dissertation, University of Victoria, Canada, 1998. 
  14. [14] Zhou Huai Lu, The Ramsey number of an odd cycle with respect to a wheel, J. Math. - Wuhan 15 (1995) 119-120. 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.