An Algorithm for graceful labelings of certain unicyclic graphs

Abstract

A graceful labeling of a simple graph $G$ is a one-to-one map $f$ from the vertices of $G$ to the set $\{0,1,2,$ $\cdots,|E(G)|\}$, such that when each edge $xy$ is assigned the label $|f(x)-f(y)|$, the resulting set of edge labels is $\{1,2,\cdots,|E(G)|\}$, with no label repeated. We are interested at Truszczynski's conjecture, that all unicyclic graphs except cycles $C_n$ with $n \equiv 1 (mod \;4)$ or $n \equiv 2 (mod\; 4)$, are graceful. Jay Bagga et al. introduced an algorithm to enumerate graceful labelings of cycles and ``sun
graphs''. We generalize their algorithm to enumerate all graceful labelings of a class of unicyclic graphs and provide some experimental results.