Ramsey Multiplicities of Graphs with Five Vertices

Abstract

The Ramsey multiplicity $M(G)$ of a graph $G$ is defined to be the smallest number of monochromatic copies of $G$ in any two-coloring of edges of $K_{R(G)}$, where $R(G)$ is the smallest integer $n$ such that every graph on $n$ vertices either contains $G$ or its complement contains $G$. With the help of computer algorithms, we obtain the exact values of Ramsey multiplicities for most of isolate-free graphs on five vertices, and establish upper bounds for a few others.