On star-critical and upper size Ramsey numbers

Yanbo Zhang, Haitze J. Broersma, Yaojun Chen

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 languageUndefined
Pages (from-to)174-180
Number of pages7
JournalDiscrete applied mathematics
Volume202
DOIs
StatePublished - 31 Mar 2016

Fingerprint

Hooks
Stars

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 -