k-graceful labeling for the Ladder graph and the Roach graph

Abstract

The study of graph labeling is currently one of the most popular graph theory research topics. Many graph labeling types can be found in graph theory. Graceful labeling is one of the most popular types of graph labeling. A simple graph G is said to be a vertex k-graceful if there exists a vertex graceful labeling on the vertices of G. A graceful labeling of G is a vertex labeling f be an injective mapping from V(G) to [0,EG+k-1] such that the edge labeling f:E(G)→[k, EG+k-1] defined by fuv=fu-f(v) is also injective. When k=1, f is called ordinary graceful labeling, and G is called a graceful graph. There is a very famous conjecture in this area that every tree is graceful. Numerous studies have been conducted on this area over the past few decades, and several results have been obtained. In this research work, we prove that the ladder graph admits the k-graceful labeling. The ladder graph is a graph obtained from the Cartesian product of Pn and P2. Moreover, we studied the k-gracefulness of the roach graphs and could obtain some partial results. However, we strongly believe that every roach graph is k-graceful. Finally, we introduced that as an open problem for future work.