Anti-Ramsey problems in the generalized Petersen graphs for cycles

Abstract

The anti-Ramsey number $Ar(G,H)$ is the maximum number of colors in an edge-coloring of $G$ with no rainbow copy of $H$. In this paper, we determine the exact anti-Ramsey number in the generalized Petersen graph $P_{n,k}$ for cycles $C_d$, where $1\le k\le \lfloor \frac{n-1}{2}\rfloor$ and $5\le d\le 6$. We also give an algorithm to obtain the upper bound or lower bound of anti-Ramsey number.