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, · · · , |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, · · · , |E(G)|}, with no label repeated. We are interested at Truszczynski’s conjecture, that all unicyclic graphs except cycles Cn with n ≡ 1(mod 4) or n ≡ 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.