Prime-Graceful Graphs

Sayan Panma, Penying Rochanakul

Abstract

A graph $G$ with $n$ vertices and $m$ edges, is said to be prime-graceful, if there is an injection $\psi:V(G)\rightarrow\{1, 2, ..., m+1\}$, where $\gcd(\psi(u),\psi(v))=1$ for all $e=\{u,v\}\in E(G)$ and the induced function  $\psi^*:E(G)\rightarrow\{1, 2, ..., m\}$ defined as  $\psi^*(e)=|\psi(u)-\psi(v)|$ is injective.

In this paper, we introduce prime-graceful labeling and show that star $K_{1,n}$, bistar $B_{n,n}$, bistar $B_{n,p-2}$, where $p$ is an odd prime, complete bipartite graph $K_{2,n}$,  tristar $SL(3,n)$, triangular book graph $B^{(3)}_n$ and some spiders are prime-graceful, while path $P_n$, cycle $C_n$ and complete graph $K_n$ are not prime-graceful in general. We also extend the idea to $k$-prime-graceful labeling  where the range of $\psi$ is extended to $\min\{kn,km\}$ for $k>1$. Next, we define the prime-graceful number to be the minimum $k$ such that $G$ is $k$-prime-graceful. Finally, we investigate the prime-graceful number of the underlying graphs.