Partial Hamming graphs and expansion procedures

AbstractStructural properties of isometric subgraphs of Hamming graphs are presented, generalizing certain results on quasi-median graphs. Consequently, a relation on the edge set of a graph which is closely related to Winkler–Djoković's relation Θ is introduced and used for a characterization of isometric subgraphs of Hamming graphs. Moreover, some results considering semi-median graphs and expansions on isometric subgraphs of hypercubes are extended to general non-bipartite case