Isometric Hamming embeddings of weighted graphs
Isometric Hamming embeddings of weighted graphs
复制标题
DOI：
10.1016/j.dam.2023.02.005
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Joseph Berleant;Kristin Sheridan;A. Condon;V. V. Williams-V.;M. Bathe
中科院分区：
文献类型：
--
作者：
Joseph Berleant;Kristin Sheridan;A. Condon;V. V. Williams-V.;M. Bathe
摘要一个映射α：如果图G中任意两个顶点之间的最短路距离等于它们在图H中的像之间的距离，则从图G的顶点集到图H的顶点集的V（G）→ V（H）是等距嵌入。在这里，我们考虑一个加权图G到未加权Hamming图的等距嵌入，称为Hamming嵌入，当G满足的性质，即每条边是它的端点之间的最短路。利用G的一个称为其典范等距表示的笛卡尔积分解，我们证明了G的每一个Hamming嵌入都可以被划分为一个典范划分，该典范划分的部分为G的典范等距表示的每一个因子提供Hamming嵌入.这意味着G允许汉明嵌入当且仅当它的正则等距表示的每个因子都是汉明可嵌入的。这一结果扩展了以前的工作，未加权图，表明一个未加权图允许汉明嵌入当且仅当每个因素是一个完整的图。当图G具有非平凡等距表示时，判定G是否具有汉明嵌入可以简化为判定两个或多个较小图的可嵌入性。
Abstract 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 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.