The ramsey number for theta graph versus a clique of order three and four

M.S.A. Bataineh; M.M.M. Jaradat; M.S. Bateeha

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 2, page 223-232
  • ISSN: 2083-5892

Abstract

top
For any two graphs F1 and F2, the graph Ramsey number r(F1, F2) is the smallest positive integer N with the property that every graph on at least N vertices contains F1 or its complement contains F2 as a subgraph. In this paper, we consider the Ramsey numbers for theta-complete graphs. We determine r(θn,Km) for m = 2, 3, 4 and n > m. More specifically, we establish that r(θn,Km) = (n − 1)(m − 1) + 1 for m = 3, 4 and n > m

How to cite

top

M.S.A. Bataineh, M.M.M. Jaradat, and M.S. Bateeha. "The ramsey number for theta graph versus a clique of order three and four." Discussiones Mathematicae Graph Theory 34.2 (2014): 223-232. <http://eudml.org/doc/267918>.

@article{M2014,
abstract = {For any two graphs F1 and F2, the graph Ramsey number r(F1, F2) is the smallest positive integer N with the property that every graph on at least N vertices contains F1 or its complement contains F2 as a subgraph. In this paper, we consider the Ramsey numbers for theta-complete graphs. We determine r(θn,Km) for m = 2, 3, 4 and n > m. More specifically, we establish that r(θn,Km) = (n − 1)(m − 1) + 1 for m = 3, 4 and n > m},
author = {M.S.A. Bataineh, M.M.M. Jaradat, M.S. Bateeha},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Ramsey number; independent set; theta graph; complete graph},
language = {eng},
number = {2},
pages = {223-232},
title = {The ramsey number for theta graph versus a clique of order three and four},
url = {http://eudml.org/doc/267918},
volume = {34},
year = {2014},
}

TY - JOUR
AU - M.S.A. Bataineh
AU - M.M.M. Jaradat
AU - M.S. Bateeha
TI - The ramsey number for theta graph versus a clique of order three and four
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 2
SP - 223
EP - 232
AB - For any two graphs F1 and F2, the graph Ramsey number r(F1, F2) is the smallest positive integer N with the property that every graph on at least N vertices contains F1 or its complement contains F2 as a subgraph. In this paper, we consider the Ramsey numbers for theta-complete graphs. We determine r(θn,Km) for m = 2, 3, 4 and n > m. More specifically, we establish that r(θn,Km) = (n − 1)(m − 1) + 1 for m = 3, 4 and n > m
LA - eng
KW - Ramsey number; independent set; theta graph; complete graph
UR - http://eudml.org/doc/267918
ER -

References

top
  1. [1] V. Chvátal and F. Harary, Generalized Ramsey theory for graphs, III. Small off- diagonal numbers, Pacific J. Math. 41 (1972) 335-345. doi:10.2140/pjm.1972.41.335[Crossref] Zbl0227.05115
  2. [2] R. Bolze and H. Harborth, The Ramsey number r(K4 − x,K5), The Theory and Applications of Graphs (Kalamazoo, MI, 1980) John Wiley & Sons, New York (1981) 109-116. 
  3. [3] L. Boza, Nuevas Cotas Superiores de Algunos Numeros de Ramsey del Tipo r(Km,Kn − e), in: Proceedings of the VII Jornada de Matematica Discreta y Algo- ritmica, JMDA 2010, Castro Urdiales, Spain July (2010). 
  4. [4] R.J. Faudree, C.C. Rousseau and R.H. Schelp, All triangle-graph Ramsey numbers for connected graphs of order six , J. Graph Theory 4 (1980) 293-300. doi:10.1002/jgt.3190040307[Crossref] Zbl0446.05035
  5. [5] M.M.M. Jaradat, M.S. Bataineh and S. Radaideh, Ramsey numbers for theta graphs, Internat. J. Combin. 2011 (2011) Article ID 649687. doi:10.1155/2011/649687 Zbl1236.05130
  6. [6] J. McNamara, Sunny Brockport, unpublished 
  7. [7] J. McNamara and S.P. Radziszowski, The Ramsey Numbers R(K4 − e,K6 − e) and R(K4 − e,K7 − e), Congr. Numer. 81 (1991) 89-96. 
  8. [8] S.P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2011) DS1 

NotesEmbed ?

top

You must be logged in to post comments.