Prime-Graceful Graphs

Abstract

A graph G with n vertices and m edges, is said to be prime-graceful, if there is an injection ψ: V (G) → {1, 2, …, m + 1}, where gcd(ψ(u), ψ(v)) = 1 for all e = {u, v} ∈ E(G) and the induced function ψ∗: E(G) → {1, 2, …, m} defined as ψ∗(e) = |ψ(u) − ψ(v)| is injective. In this paper, we introduce prime-graceful labeling and show that star K1,n, bistar Bn,n, bistar Bn,p−2, where p is an odd prime, complete bipartite graph K2,n, tristar SL(3, n), triangular book graph Bn(3) and some spiders are prime-graceful, while path Pn, cycle Cn and complete graph Kn are not prime-graceful in general. We also extend the idea to k-prime-graceful labeling where the range of ψ is extended to k min{n, m} 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.