Generalized Ramsey theory for graphs IV, the Ramsey multiplicity of a graph
Abstract
A Proper graph G has no isolated points. Its Ramsey number r(G) is the minimum p such that every 2-coloring of the edges of Kp contains a monochromatic G. The Ramsey multiplicity R(G) is the minimum number of monochromatic G in any 2-coloring of Kr(G). With just one exception, namely K4, we determine R(G) for proper graphs with at most 4 points. For the stars K1,n, it is shown that R = 2n when n is odd and R = 1 when n is even. We conclude with the conjecture that for a proper graph, R(G) = 1 if and only if G = K2 or K1,n with n even.