Partial Hamming graphs and expansion procedures (Q5939915)

A graph \(G\) is a partial Hamming graph (an isometric subgraph of a Hamming graph) if its vertices can be labeled by words (or labels) of a fixed length over some finite alphabet and having certain properties of the distance (Hamming distance) between any two vertices in \(G\). In the present paper, at first a detailed survey on considerations of these graphs and related classes in the last thirty years is given and then the author proves numerous new properties by using known properties of partial Hamming graphs. Among other things, he introduces a certain relation \(\Delta\) on the edge set of a connected graph, since the transitivity of \(\Delta\) is a basic condition for new characterizations of partial Hamming graphs. Further, a connected and an isometric expansion are defined, and in the two Theorems 17 and 18 it is shown that on the one hand so-called semi-quasi-median graphs can be obtained by this connected expansion procedure from a one-vertex-graph and, on the other hand, this isometric expansion procedure always produces semi-quasi-median graphs. Thus, the author obtains generalizations of semi-median-graphs. It follows the abstract of the author: Structural 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 the Winkler-Djoković relation \(\Theta\) is introduced and used for a characterization of isometric subgraphs of Hamming graphs. Moreover, some results concerning semi-median graphs and expansions on isometric subgraphs of hypercubes are extended to the general non-bipartite case.