Complete k-ary trees and Hamming graphs

A Hamming graph H(b, n)of base b and dimension n has vertex set {X = x 1x2 ...xn : xi ∈{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, Thk, 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) (log 32)(h+l)⌉≤m(3,2,h)≤ ̧2/3(h+l)⌉, (iii) h+l/log2 b < m(b, 2,h) < h+l/&ifloor;log2 b⌋, for every b ≠ 2l,and that (iv) h+l/log2b ≤ m(b, 2,h) ≤ h+2/log2 b for every b = 2l.