On the Restricted Size Ramsey Number Involving a Path P3

摘要

For any pair of graphs G and H , both the size Ramsey number ? r ( G,H ) and the restricted size Ramsey number r *( G,H ) are bounded above by the size of the complete graph with order equals to the Ramsey number r ( G,H ), and bounded below by e ( G ) + e ( H ) ? 1. Moreover, trivially, ? r ( G,H ) ≤ r *( G,H ). When introducing the size Ramsey number for graph, Erd?s et al. (1978) asked two questions; (1) Do there exist graphs G and H such that ? r ( G,H ) attains the upper bound? and (2) Do there exist graphs G and H such that ? r ( G,H ) is significantly less than the upper bound?In this paper we consider the restricted size Ramsey number r *( G,H ). We answer both questions above for r *( G,H ) when G = P _(3) and H is a connected graph.