Isometric Hamming embeddings of weighted graphs

Abstract

A mapping $\alpha :V\left(G\right)\to V\left(H\right)$ from the vertex set of one graph $G$ to another graph $H$ is an isometric embedding if the shortest path distance between any two vertices in $G$ equals the distance between their images in $H$. Here, we consider isometric embeddings of a weighted graph $G$ into unweighted Hamming graphs, called Hamming embeddings, when $G$ satisfies the property that every edge is a shortest path between its endpoints. Using a Cartesian product decomposition of $G$ called its canonical isometric representation, we show that every Hamming embedding of $G$ may be partitioned into a canonical partition, whose parts provide Hamming embeddings for each factor of the canonical isometric representation of $G$. This implies that $G$ permits a Hamming embedding if and only if each factor of its canonical isometric representation is Hamming embeddable. This result extends prior work on unweighted graphs that showed that an unweighted graph permits a Hamming embedding if and only if each factor is a complete graph. When a graph $G$ has nontrivial isometric representation, determining whether $G$ has a Hamming embedding can be simplified to checking embeddability of two or more smaller graphs.

Keywords: Graph embeddings; Graph factorization; Hamming graphs; Isometric embeddings; Metric spaces; Weighted graphs.

Fig. 1.

Embedding weighted graphs is more difficult than unweighted graphs, and some guarantees for unweighted graphs no longer hold. (a) A simple graph which permits a Hamming embedding into ${\left(K_2\right)}^4\times {\left(K_3\right)}^2$, but which is not covered by previous theorems on isometric embeddings of weighted graphs. (b) A weighted graph that permits a hypercube embedding, but for which the unweighted graph generated via edge subdivision is not. (c) A weighted graph, $K_4$ with uniform edge weights of 2, for which multiple non-equivalent hypercube embeddings exist.

Fig. 2.

(a) Illustration of the Cartesian graph product. Edge colors indicate correspondence between edges in the factor and product graphs. If edges are weighted, two edges of the same color will have the same weight. (b) This graph product is isometrically embeddable in a product of three irreducible graphs ($K_3,K_2$, and $K_2$), which form the factors of its canonical isometric representation. (c) A weighted graph, with purple edges of weight 4 and orange edges of weight 2. Edge colors also indicate equivalence classes under the transitive closure $\hat{\theta }$ of the Djoković-Winkler relation (d) A hypercube embedding of this graph, with digits colored to indicate equivalence classes under $\hat{\gamma }.\hat{\gamma }$ is the transitive closure of $\gamma$, which relates coordinates whose digits change together across some edge. (e) Our results show that the hypercube embedding in (d) may be partitioned into a hypercube embedding for each factor. The same is true of any Hamming embedding of a weight-minimal graph.