A Hamming graph H(b, n) of base b and dimension n has vertex set {X = x(1)x(2)... x(n) : x(i) is an element of{0, 1,..., b - 1}, for 1 <= i <= n} and edge set {(X, Y) : X and Y differ in exactly one bit position}. In this paper, we are concerned with the following problem: Given positive integers b, k and h, what is the minimum integer m - m( b, k, h) such that the complete k-ary tree, T-h(k), of height h, is a subgraph of H(b, m)? The value m(b, k, h) is known for very few values of b, k and h. We show that (i) m(k, k, h) - h + 1, for every k >= 3, (ii) inverted right perpendicular(log(3) 2)( h + 1) inverted left perpendicular <= m(3, 2, h) = <= inverted right perpendicular2/3(h + 1)inverted left perpendicular (iii)inverted right perpendicular h+1/log(2)b inverted left perpendicular <= m(b, 2, h) <= inverted right perpendicularh + 1/ inverted right perpendicularlog2 binverted left perpendicular inverted left perpendicular , for every b not equal 2(l), and that (iv) inverted right perpendicular h + 1 log(2)b inverted left perpendicular <= m(b, 2, h) <= inverted right perpendicular h+ 2 log(2)b,inverted left perpendicular for every b = 2(l).
