Locally constrained graph homomorphisms-structure, complexity, and applications
Locally constrained graph homomorphisms-structure, complexity, and applications
复制标题
DOI：
10.1016/j.cosrev.2008.06.001
复制
发表时间：
2008-08-01
影响因子：
12.9
通讯作者：
Kratochvil, Jan
中科院分区：
文献类型：
--
作者：
Fiala, Jiri;Kratochvil, Jan
图同态是两个图之间的边保持顶点映射。局部约束同态是那些在顶点邻域上表现良好的同态。如果源图的任何顶点的邻域被双射（内射，满射）映射到其在目标图中的像的邻域，则同态被称为局部双射（分别为内射，满射）。我们表明，这种观点统一了以前研究的问题，从不同的角度和不同的名称，如图覆盖，距离约束图标签，或角色分配。我们的调查提供了一个概述的应用程序，复杂性的结果，相关的问题，和历史笔记局部约束图同态。(C)2008年爱思唯尔公司All rights reserved.
A graph homomorphism is an edge preserving vertex mapping between two graphs. Locally constrained homomorphisms are those that behave well on the neighborhoods of vertices. If the neighborhood of any vertex of the source graph is mapped bijectively (injectively, surjectively) to the neighborhood of its image in the target graph, the homomorphism is called locally bijective (injective, surjective, respectively). We show that this view unifies issues studied before from different perspectives and under different names, such as graph covers, distance constrained graph labelings, or role assignments. Our survey provides an overview of applications, complexity results, related problems, and historical notes on locally constrained graph homomorphisms. (C) 2008 Elsevier Inc. All rights reserved.