On the large maximal {0,1,2, ..., t }-cliques in Hamming graph H(n,q)

Abstract

A set of vertices ℱ of a graph is called a t-clique if d(x, y) ≤ t for any two vertices x and y in ℱ. For the Hamming graph H(n, q) which has a vertex set H = Xⁿ, the Cartesian product of a q-set X, and two vertices of u and v are adjacent whenever they differ in precisely one entry, Hemmeter showed that there is only one isomorphism class of maximal 1-cliques. In this paper, we show that H(n, q) (n ≥ 3) has exactly 3 isomorphism classes of maximal 2-cliques, and classify asymptotically large maximal t-cliques of H(n, q).