Graceful Labeling of Paths and 3-Branch-Trees

Eric Chiang, Simon Fraser University and University of Waterloo

A Graceful Labeling of a graph G with q edges is an injection f:V(G) -> {0,1,2...,q} such that when each edge xy in E(G) is assigned the label, |f(x)-f(y)|, all of the edge labels are distinct. The famous Graceful Tree Conjecture states that every tree has a graceful labelling. We look at two kinds of special trees (paths and 3-branch trees) and investigate the conditions required for their graceful labelings.