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 \leq i \leq n-1, (12)(34)\ldots(2m-1, 2m), 1 \leq m \leq \frac{n}{2}\), and give some general results.