On The Harmonious Colouring of Trees

Let G be a simple graph. A harmonious colouring of G is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colours in such a colouring. In this paper it is shown that if T is a tree of order n and Delta(T) >= n/2 then h(T) = Delta(T) + 1, where Delta(T) denotes the maximum degree of T. Let T-1 and T-2 be two trees of order n(1) and n(2), respectively and F = T-1 boolean OR T-2. In this paper it is shown that if Delta(T-i) = Delta(i) and Delta(i) >= n(i)/2, for i = 1, 2, then h(F) <= Delta(F) + 2. Moreover, if Delta(1) = Delta(2) = Delta >= n(i)/2, for i = 1, 2, then h(F) = Delta + 2.