On the Graceful Conjecture of Permutation Graphs of Paths

Abstract

S.M. Lee proposed the conjecture: for any $n>1$ and any permutation $f$ in $S(n)$, the permutation graph $P(P_n,f)$ is graceful. For any integer $n>1$, we discuss gracefulness of the permutation graphs $P(P_n,f)$ when $f=(123),(n-2,n-1,n),(i,i+1),1\le i\le n-1,(12)(34)\dots (2m-1,2m),1\le m\le \frac{n}{2}$, and give some general results.