Article ID Journal Published Year Pages File Type
4649713 Discrete Mathematics 2008 4 Pages PDF
Abstract

For given graphs GG and H,H, the Ramsey number R(G,H)R(G,H) is the smallest natural number nn such that for every graph FF of order nn: either FF contains GG or the complement of FF contains H.H. In this paper we investigate the Ramsey number of a disjoint union of graphs R(⋃i=1kGi,H). For any natural integer k  , we contain a general upper bound, R(kG,H)⩽R(G,H)+(k-1)|V(G)|R(kG,H)⩽R(G,H)+(k-1)|V(G)|. We also show that if m=2n-4m=2n-4, 2n-82n-8 or 2n-62n-6, then R(kSn,Wm)=R(Sn,Wm)+(k-1)nR(kSn,Wm)=R(Sn,Wm)+(k-1)n. Furthermore, if |Gi|>(|Gi|-|Gi+1|)(χ(H)-1)|Gi|>(|Gi|-|Gi+1|)(χ(H)-1) and R(Gi,H)=(χ(H)-1)(|Gi|-1)+1R(Gi,H)=(χ(H)-1)(|Gi|-1)+1, for each ii, then R(⋃i=1kGi,H)=R(Gk,H)+∑i=1k-1|Gi|.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,