Subdivided graphs as isometric subgraphs of Hamming graphs

AbstractIsometric subgraphs of Hamming graphs (resp. hypercubes) are called partial Hamming graphs (resp. partial cubes). In this paper we look for structural characterizations of subdivided cliques that are partial Hamming graphs. It is proven that given G a subdivision of a clique Kn (n≥1), G is isometrically embeddable in a Hamming graph if and only if G is a partial cube or G=Kn. The characterization for subdivided wheels is also obtained