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.