On the Edge-Gracefulness of Water Wheel-Type Graphs and Their Splitting Graphs

Abstract

A graph $G$ with $p$ vertices and $q$ edges is said to be edge-graceful if its edges can be labeled from $1$ through $q$, in such a way that the labels induced on the vertices by adding over the labels of incident edges modulo $p$ are distinct. Lo's Theorem is a known result under this topic, which states that if a graph $G$ with $p$ vertices and $q$ edges is edge-graceful, then $p\Big|\Big(q^{2}+q-\frac{p(p-1)}{2}\Big)$. Since the introduction of the concept of edge-graceful labeling, several works on the edge-graceful labeling of specific families of graphs have been conducted. This paper recalls the definition of water wheel graphs $(WW_n)$ and introduces two new related graphs, the right water wheel graphs $(RWW_n)$ and left water wheel graphs $(LWW_n)$. Next, using Lo's Theorem, and the concepts of divisibility and Diophantine equations, we proved the non-edge-gracefulness of these graphs. Then, using the same concepts, we determine all the edge-graceful splitting graphs of $WW_n$, $RWW_n$, and $LWW_n$, denoted as $S(WW_n)$, $S(RWW_n)$, and $S(LWW_n)$, respectively. Finally, Python computer programs were created and used to conclude that among these graph families, only $S(WW_3)$, $S(RWW_3)$, and $S(LWW_3)$ are edge-graceful, by providing their corresponding edge-graceful labels.