Some exact values on Ramsey numbers related to fans

Abstract

For two given graphs $F$ and $H$, the Ramsey number $R(F,H)$ is the smallest integer $N$ such that any red-blue edge-coloring of the complete graph $K_N$ contains a red $F$ or a blue $H$. When $F=H$, we simply write $R_2(H)$. For an positive integer $n$, let $K_{1,n}$ be a star with $n+1$ vertices, $F_n$ be a fan with $2n+1$ vertices consisting of $n$ triangles sharing one common vertex, and $n{K}_3$ be a graph with $3n$ vertices obtained from the disjoint union of $n$ triangles. In 1975, Burr, Erdős and Spencer \cite{B} proved that $R_2(n{K}_3)=5n$ for $n\ge 2$. However, determining the exact value of $R_2(F_n)$ is notoriously difficult. So far, only $R_2(F_2)=9$ has been proved. Notice that both $F_n$ and $n{K}_3$ contain $n$ triangles and $|V(F_n)|<|V(n{K}_3)|$ for all $n\ge 2$. Chen, Yu and Zhao (2021) speculated that $R_2(F_n)\le R_2(n{K}_3)=5n$ for $n$ sufficiently large. In this paper, we first prove that $R(K_{1,n},F_n)=3n-\epsilon$ for $n\ge 1$, where $\epsilon =0$ if $n$ is odd and $\epsilon =1$ if $n$ is even. Applying the exact values of $R(K_{1,n},F_n)$, we will confirm $R_2(F_n)\le 5n$ for $n=3$ by showing that $R_2(F_3)=14$.

10 pages, 3 figures