2021/12/13 by Joseph Berleant, Kristin Sheridan, Berleant, Joseph +7
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.2112.06994
14 pages, 2 figures; fixed author affiliations
arxiv created 2021/12/20 · arxiv updated 2021/12/21
A mapping α: V(G) → V(H) 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 pseudofactorization, we show that every Hamming embedding of G may be partitioned into Hamming embeddings for each irreducible pseudofactor graph of G, which we call its canonical partition. This implies that G permits a Hamming embedding if and only if each of its irreducible pseudofactors 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 irreducible pseudofactor is a complete graph. When a graph G has nontrivial pseudofactors, determining whether G has a Hamming embedding can be simplified to checking embeddability of two or more smaller graphs.