Article ID Journal Published Year Pages File Type
419010 Discrete Applied Mathematics 2015 5 Pages PDF
Abstract

Let Sk=K1,kSk=K1,k be a star of kk edges, and let Kn⊔SkKn⊔Sk be a graph obtained from KnKn and an additional vertex vv by joining vv and kk vertices of KnKn. For graphs GG and HH, let r=r(G,H)r=r(G,H) be the Ramsey number of GG and HH. The star-critical Ramsey number r∗(G,H)r∗(G,H) is the smallest kk such that every red/blue edge-coloring of Kr−1⊔SkKr−1⊔Sk contains a red GG or a blue HH. In this note, we show that r∗(Kn,mK2)=n+2m−3r∗(Kn,mK2)=n+2m−3 for m≥1m≥1 and n>2n>2, r∗(Fn,K3)=2n+2r∗(Fn,K3)=2n+2 for n≥2n≥2, where FnFn is an nn-fan. We also show that r∗(nK4,mK3)=4n+2mr∗(nK4,mK3)=4n+2m for n≥m≥1n≥m≥1 and n≥2n≥2, and r∗(nK4,mK3)=3n+3mr∗(nK4,mK3)=3n+3m for m≥n≥2m≥n≥2.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,