Research Problem 2
by I. Cahit
Embedding trees gracefully onto the triangular grids

We have proposed an equivalent problem of graceful labeling of trees as an embedding problem which was pointed first in [1]. To do this we first consider the triangular grid D consisted of (n-1) parallel horizontal, left and right diagonal lines plus with an extra horizontal line which we call the reflection line. Now place the vertices of the given (n-1)-vertex tree T on the cross points of D in such a way that

  1. only single vertex will be placed on each horizontal lines, of the cross points of D and
  2. the traces of the embedded vertices would cover all left and right diagonal lines.
Where the trace of an vertex is obtained by traversing left and right diagonal lines in both directions, starting from that vertex. The trace of a vertex continues after hitting the reflection line in the natural way.

If T is any tree with n-1 vertices with maximum vertex degree three then show that there exits one to one correspondences between the gracefully labeled tree and the tree embedded in this way. See the figure below for the illustration of  the tree embedding problem.

[1] S.R. Cornejo, "Metodo para obtoner familias infinitas de grafos graciosos", Review SIGMA,  5(1), PP.19-49.