Conjecture on Odd Graceful Graphs

Abstract

A graph \( G = (V, E) \) with \( p \) vertices and \( q \) edges is said to be odd graceful if there is an injection \( f \) from the vertex set of \( G \) to \( \{0, 1, 2, \dots, 2q – 1\} \) such that when each edge \( xy \) is assigned the label \( |f(x) – f(y)| \), the resulting edge labels are distinct and induce the set \( \{1, 3, 5, \dots, 2q – 1\} \). In 2009, Barrientos conjectured that every bipartite graph is odd graceful. In this paper, we partially solve Barrientos’ conjecture by showing that the following graphs are odd graceful:

1. Finite union of paths, stars, and caterpillars;
2. Finite union of ladders;
3. Finite union of paths, bistars, and caterpillars;
4. The coronas \( K_{m,n} \odot K_1 \); and
5. Finite union of graphs obtained by one endpoint union of an odd number of paths of uniform length.