WikiEdge:ArXiv-2409.05678v1/methods

编辑

这篇论文的工作部分详细介绍了如何研究平面n, m-图的类比四色定理问题。以下是这部分的主要内容：

1. (n, m)-图的定义：
   • 定义了(n, m)-图的概念，即一个图包含n种类型的弧和m种类型的边，每种类型的弧或边用不同的符号标记。
2. (n, m)-完全图的性质：
   • 研究了(n, m)-完全图的性质，这是没有环路或多重边的图，并且任意两个顶点的识别会导致具有不同标签的环路或并行邻接。
3. 平面(n, m)-完全图的顶点数上界：
   • 证明了对于所有(n, m) ≠ (0, 1)，平面(n, m)-完全图的顶点数不能超过3(2n+m)^2 + (2n+m) + 1，并且这个界限是紧确的。
4. 特殊2-路径和邻接关系：
   • 使用特殊2-路径的概念来表征(n, m)-完全图，即如果两个顶点通过特殊2-路径相连，则它们必须相互“看见”。
5. 支配数和区域划分：
   • 利用图的支配数和区域划分来构建证明，特别是当支配数为2时，详细分析了图的结构特性。
6. 计数和平面嵌入障碍：
   • 结合计数和平面图的嵌入障碍来处理证明中的一部分，特别是当(n, m)的值较大时，如何避免指数级增长的子情况。
7. 应用和动机：
   • 讨论了(n, m)-图同态在图数据库查询评估问题中的应用，以及它们在社交网络、信息网络、技术网络和生物网络中的潜在用途。