Premium
Generalized Ramsey theory for graphs IV, the Ramsey multiplicity of a graph
Author(s) -
Harary F.,
Prins G.
Publication year - 1974
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230040206
Subject(s) - combinatorics , monochromatic color , mathematics , conjecture , ramsey's theorem , multiplicity (mathematics) , graph , ramsey theory , discrete mathematics , edge coloring , graph power , physics , line graph , optics , mathematical analysis
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 K p contains a monochromatic G. The Ramsey multiplicity R(G) is the minimum number of monochromatic G in any 2‐coloring of K r(G) . With just one exception, namely K 4 , we determine R(G) for proper graphs with at most 4 points. For the stars K 1,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 = K 2 or K 1,n with n even.