Abstract:
The concept of rainbow connection was introduced by Chartrand et al.. It has become
a new and active subject in graph theory. On this topic a book was written by Li and
Sun and there is a survey paper also by Li, Shi and Sun. From then many researches on
rainbow edge coloring is going on. Krivelevich and Yuster have defined vertex variant on
rainbow connection. On rainbow vertex connection also research has been started from
then. Rainbow vertex coloring on powers of trees have been solved in [9]. They gave a
linear time algorithm to color vertices such that the graph will be rainbow vertex connected.
In our knowledge rainbow edge coloring on powers of trees has not been solved yet. In
this work we will use similar type of idea of rainbow vertex coloring to find rainbow edge
coloring on powers of trees. We will give a linear time algorithm to color edges such that
the graph will be rainbow edge connected. Sudipta Ghosh worked on squares of trees in
his M.Tech Dissertation and in this work I will extend his work for higher power of trees.