The harmonious chromatic number of complete r-ary trees

A harmonious colouring of a simple graph 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. We define Q(m) to be the least positive integer k such that ((k)(2)) greater than or equal to m. Then h(G) greater than or equal to Q(m) for any graph G with m edges. We consider the complete r-ary tree of height H, denoted T-r,T-H. We show that for any r greater than or equal to 2, H greater than or equal to 3, if m is the number of edges of T-r,T-H, then h(T-r,T-H) = Q(m), except that h(T-2,T-3) = 7. (C) 1999 Elsevier Science B.V. All rights reserved.