⚠️ 以下所有内容总结都来自于 大语言模型的能力，如有错误，仅供参考，谨慎使用
🔴 请注意：千万不要用于严肃的学术场景，只能用于论文阅读前的初筛！
💗 如果您觉得我们的项目对您有帮助 ChatPaperFree ，还请您给我们一些鼓励！⭐️ HuggingFace免费体验
2025-04-26 更新
Graph covers and semi-covers: Who is stronger?
Authors:Jan Kratochvil, Roman Nedela
The notion of graph cover, also known as locally bijective homomorphism, is a discretization of covering spaces known from general topology. It is a pair of incidence-preserving vertex- and edge-mappings between two graphs, the edge-component being bijective on the edge-neighborhoods of every vertex and its image. In line with the current trends in topological graph theory and its applications in mathematical physics, graphs are considered in the most relaxed form and as such they may contain multiple edges, loops and semi-edges. Nevertheless, simple graphs (binary structures without multiple edges, loops, or semi-edges) play an important role. It has been conjectured in [Bok et al.: List covering of regular multigraphs, Proceedings IWOCA 2022, LNCS 13270, pp. 228–242] that for every fixed graph $H$, deciding if a graph covers $H$ is either polynomial time solvable for arbitrary input graphs, or NP-complete for simple ones. A graph $A$ is called stronger than a graph $B$ if every simple graph that covers $A$ also covers $B$. This notion was defined and found useful for NP-hardness reductions for disconnected graphs in [Bok et al.: Computational complexity of covering disconnected multigraphs, Proceedings FCT 2022, LNCS 12867, pp. 85–99]. It was conjectured in [Kratochv'{\i}l: Towards strong dichotomy of graphs covers, GROW 2022 - Book of open problems, p. 10, {\tt https://grow.famnit.upr.si/GROW-BOP.pdf}] that if $A$ has no semi-edges, then $A$ is stronger than $B$ if and only if $A$ covers $B$. We prove this conjecture for cubic one-vertex graphs, and we also justify it for all cubic graphs $A$ with at most 4 vertices.
图覆盖的概念，也称为局部双射同态，是源自一般拓扑学的覆盖空间的离散化。它是两个图之间保持发生关系的顶点和边映射对，边组件在每个顶点的边邻域及其图像上是双射的。根据目前拓扑图论及其在数学物理中的应用趋势，图以最放松的形式考虑，因此它们可能包含多条边、循环和半边。尽管如此，简单图（没有多条边、循环或半边的二元结构）扮演着重要角色。在[Bok等人：正则多图的列表覆盖，IWOCA 2022会议论文集，LNCS 13270，第228-242页]中猜想，对于每个固定图H，判断一个图是否覆盖H要么是针对任意输入图的多项式时间可解决的，要么是对于简单图的NP完全问题。如果一个图A被称为强于另一个图B，那么每一个覆盖A的简单图也覆盖B。这一概念在[Bok等人：不连通多图的覆盖计算复杂性，FCT 2022会议论文集，LNCS 12867，第85-99页]中被定义并发现对于不连通图的NP难度降低很有用。在[Kratochv’il：图覆盖的强二分法趋向，GROW 2022 - 开放问题集，第10页，{\tt https://grow.famnit.upr.si/GROW-BOP.pdf}]中猜想，如果A没有半边，那么A强于B当且仅当A覆盖B。我们证明了立方单顶点图的这一猜想，并为所有最多4个顶点的立方图A证明了这一点。
论文及项目相关链接
Summary
图覆盖的概念，又称为局部双射同态，是覆盖空间离散化的概念，源于一般拓扑学。它是一对图之间的顶点映射和边映射，这些映射在保持发生率的同时，对每顶点的边邻域及其映像进行边组件的双射。在拓扑图论及其在数学物理中的应用的当前趋势下，图以最放松的形式考虑，可能包含多条边、循环和半边。然而，简单图（没有多条边、循环或半边的二元结构）起着重要作用。关于固定图H的覆盖问题，对于任意输入图是多项式时间可解决的，或者对于简单图是NP完全的，这一猜想在[Bok et al.的文献中提出。一个图A被称为强于图B，如果任何覆盖A的简单图也覆盖B。这一概念在[Bok et al.]的文献中被定义并用于NP硬度减少的不连通图中发现很有用。在[Kratochv’il的猜想中，如果没有半边，那么A强于B当且仅当A覆盖B。我们证明了立方单顶点图的这一猜想，并为所有最多4个顶点的立方图A证明了合理性。
Key Takeaways
- 图覆盖概念是覆盖空间的离散化，用于描述两个图之间的顶点映射和边映射关系。
- 在拓扑图论中，图的定义可以包含多种形态，如多重边、循环和半边。
- 简单图在研究中具有重要地位。
- 关于固定图的覆盖问题存在多项式时间解决或NP完全问题的猜想。
- 图A被称为强于图B，如果任何覆盖A的图也覆盖B。这一概念在NP硬度降低的不连通图中尤为重要。
- 对于没有半边的图，存在一猜想认为图A强于B等价于A覆盖B。
点此查看论文截图
