On star-critical and upper size Ramsey numbers

Yanbo Zhang, Haitze J. Broersma, Yaojun Chen

  • 1 Citations

Abstract

In this paper, we study the upper size Ramsey number u(G1,G2)u(G1,G2), defined by Erdős and Faudree, as well as the star-critical Ramsey number r∗(G1,G2)r∗(G1,G2), defined by Hook and Isaak. We define Ramsey-full graphs and size Ramsey good graphs, and perform a detailed study on these graphs. We generalize earlier results by determining u(nKk,mKl)u(nKk,mKl) and r∗(nKk,mKl)r∗(nKk,mKl) for k,l≥3k,l≥3 and large m,nm,n; u(Cn,Cm)u(Cn,Cm) for mm odd, with n>m≥3n>m≥3; and r∗(Cn,Cm)r∗(Cn,Cm) for mm odd, with n≥m≥3n≥m≥3 and (m,n)≠(3,3)(m,n)≠(3,3).
Original languageEnglish
Pages (from-to)174-180
Number of pages7
JournalDiscrete applied mathematics
Volume202
DOIs
StatePublished - 31 Mar 2016

Fingerprint

Stars
Hooks

Keywords

  • EWI-26837
  • MSC-05C
  • Upper size Ramsey number
  • IR-99581
  • Ramsey-full graph
  • Star-critical Ramsey number
  • METIS-316047
  • Size Ramsey good graph

Cite this

Zhang, Yanbo; Broersma, Haitze J.; Chen, Yaojun / On star-critical and upper size Ramsey numbers.

In: Discrete applied mathematics, Vol. 202, 31.03.2016, p. 174-180.

Research output: Scientific - peer-reviewArticle

@article{e22b5df84af74442ba084a280f1c0481,
title = "On star-critical and upper size Ramsey numbers",
abstract = "In this paper, we study the upper size Ramsey number u(G1,G2)u(G1,G2), defined by Erdős and Faudree, as well as the star-critical Ramsey number r∗(G1,G2)r∗(G1,G2), defined by Hook and Isaak. We define Ramsey-full graphs and size Ramsey good graphs, and perform a detailed study on these graphs. We generalize earlier results by determining u(nKk,mKl)u(nKk,mKl) and r∗(nKk,mKl)r∗(nKk,mKl) for k,l≥3k,l≥3 and large m,nm,n; u(Cn,Cm)u(Cn,Cm) for mm odd, with n>m≥3n>m≥3; and r∗(Cn,Cm)r∗(Cn,Cm) for mm odd, with n≥m≥3n≥m≥3 and (m,n)≠(3,3)(m,n)≠(3,3).",
keywords = "EWI-26837, MSC-05C, Upper size Ramsey number, IR-99581, Ramsey-full graph, Star-critical Ramsey number, METIS-316047, Size Ramsey good graph",
author = "Yanbo Zhang and Broersma, {Haitze J.} and Yaojun Chen",
note = "eemcs-eprint-26837",
year = "2016",
month = "3",
doi = "10.1016/j.dam.2015.08.020",
volume = "202",
pages = "174--180",
journal = "Discrete applied mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

On star-critical and upper size Ramsey numbers. / Zhang, Yanbo; Broersma, Haitze J.; Chen, Yaojun.

In: Discrete applied mathematics, Vol. 202, 31.03.2016, p. 174-180.

Research output: Scientific - peer-reviewArticle

TY - JOUR

T1 - On star-critical and upper size Ramsey numbers

AU - Zhang,Yanbo

AU - Broersma,Haitze J.

AU - Chen,Yaojun

N1 - eemcs-eprint-26837

PY - 2016/3/31

Y1 - 2016/3/31

N2 - In this paper, we study the upper size Ramsey number u(G1,G2)u(G1,G2), defined by Erdős and Faudree, as well as the star-critical Ramsey number r∗(G1,G2)r∗(G1,G2), defined by Hook and Isaak. We define Ramsey-full graphs and size Ramsey good graphs, and perform a detailed study on these graphs. We generalize earlier results by determining u(nKk,mKl)u(nKk,mKl) and r∗(nKk,mKl)r∗(nKk,mKl) for k,l≥3k,l≥3 and large m,nm,n; u(Cn,Cm)u(Cn,Cm) for mm odd, with n>m≥3n>m≥3; and r∗(Cn,Cm)r∗(Cn,Cm) for mm odd, with n≥m≥3n≥m≥3 and (m,n)≠(3,3)(m,n)≠(3,3).

AB - In this paper, we study the upper size Ramsey number u(G1,G2)u(G1,G2), defined by Erdős and Faudree, as well as the star-critical Ramsey number r∗(G1,G2)r∗(G1,G2), defined by Hook and Isaak. We define Ramsey-full graphs and size Ramsey good graphs, and perform a detailed study on these graphs. We generalize earlier results by determining u(nKk,mKl)u(nKk,mKl) and r∗(nKk,mKl)r∗(nKk,mKl) for k,l≥3k,l≥3 and large m,nm,n; u(Cn,Cm)u(Cn,Cm) for mm odd, with n>m≥3n>m≥3; and r∗(Cn,Cm)r∗(Cn,Cm) for mm odd, with n≥m≥3n≥m≥3 and (m,n)≠(3,3)(m,n)≠(3,3).

KW - EWI-26837

KW - MSC-05C

KW - Upper size Ramsey number

KW - IR-99581

KW - Ramsey-full graph

KW - Star-critical Ramsey number

KW - METIS-316047

KW - Size Ramsey good graph

U2 - 10.1016/j.dam.2015.08.020

DO - 10.1016/j.dam.2015.08.020

M3 - Article

VL - 202

SP - 174

EP - 180

JO - Discrete applied mathematics

T2 - Discrete applied mathematics

JF - Discrete applied mathematics

SN - 0166-218X

ER -