ESD Labeling in Unicyclic Graphs

A labeling $ESD$ for a graph $G = (V, E)$ is an injective function $f: V \rightarrow \{1,2,\ldots,s\}$, which induces an edge labeling $\varphi(vw)=f(v)+f(w)$ such that the labels obtained for the edges are all distinct. When the largest label used is limited to $(s=n)$, the labeling is called canonical ESD. In this work, the open problem of determining whether every unicyclic graph possesses a canonical (ESD) labeling was solved. In addition to proving that every unicyclic graph possesses a canonical (ESD) labeling, a linear algorithm for obtaining this labeling was developed.