What is Ramsey-equivalent to a clique?

A graph G is Ramsey for H if every two-colouring of the edges of G contains a monochromatic copy of H. Two graphs H and H ' are Ramsey-equivalent if every graph G is Ramsey for H if and only if it is Ramsey for H ' . In this paper, we study the problem of determining which graphs are Ramsey-equivalent to the complete graph K k . A famous theorem of Nesetřil and Rodl implies that any graph H which is Ramsey-equivalent to K k must contain K k . We prove that the only connected graph which is Ramsey-equivalent to K k is itself. This gives a negative answer to the question of Szabo, Zumstein, and Zurcher on whether K k is Ramsey-equivalent to K k ? K 2 , the graph on k + 1 vertices consisting of K k with a pendent edge.In fact, we prove a stronger result. A graph G is Ramsey minimal for a graph H if it is Ramsey for H but no proper subgraph of G is Ramsey for H. Let s ( H ) be the smallest minimum degree over all Ramsey minimal graphs for H. The study of s ( H ) was introduced by Burr, Erd?s, and Lovasz, where they show that s ( K k ) = ( k - 1 ) 2 . We prove that s ( K k ? K 2 ) = k - 1 , and hence K k and K k ? K 2 are not Ramsey-equivalent.We also address the question of which non-connected graphs are Ramsey-equivalent to K k . Let f ( k , t ) be the maximum f such that the graph H = K k + f K t , consisting of K k and f disjoint copies of K t , is Ramsey-equivalent to K k . Szabo, Zumstein, and Zurcher gave a lower bound on f ( k , t ) . We prove an upper bound on f ( k , t ) which is roughly within a factor 2 of the lower bound.