Exploring the Oriented Graceful Labeling Conjecture on Lobster Trees

Timothy Nosco, Lisa Jones, Jakub Smola, Jessie Lass, Jocelyn Bell, William Pulleyblank, Suzanne J Matthews, Christopher Okasaki


Introduced in 1967 by Rosa and further explored by Ringel and Kotzig, the famously unsolved graceful tree labeling conjecture (GTL) is a labeling problem in graph theory which proposes that for any tree with m+1 vertices, each vertex can be assigned a distinct label from 0 to m such that if we assign to each edge the absolute value of the difference of its adjacent vertices, then every edge is assigned a distinct value between 1 and m. This conjecture has been proven to hold for certain families of trees, but no proof for the general conjecture has been found. In 2015, Bell et al. presented a stricter version of GTL known as the oriented graceful tree labeling conjecture (OTL), imposing the additional constraint that for every vertex v in a tree T, the labels of vertices adjacent to v are either all strictly less than the label of v, or all strictly greater than the label of v. Our contribution addresses the mathematical community’s desire for a computational toolset to assist in the exploration of these graph labeling conjectures, particularly on lobster tree topologies. Using Python, parallel computing, and Microsoft’s Z3 SMT solver, we are able to verify the conjecture for lobster trees up to 19 vertices. We plan to continue developing this toolset and eventually make it available to the public as an open-source project.


Graceful Tree Labeling Conjecture; Oriented Tree Labeling Conjecture; Lobster Tree; Message Passing; Parallel Computing

Full Text: PDF


  • There are currently no refbacks.