通过计算路径来对一个任意的循环图进行“封圣”（即确定其特殊性质）

《Combinatorics, Probability and Computing》：Canonization of a random circulant graph by counting walks

颜色精炼与顶点个体化结合可对几乎全部循环有向图生成规范标签，无需完整颜色精炼算法，同时验证其Tinhofer紧致性并构建二维Weisfeiler-Leman算法下的规范Cayley表示。

　　

摘要

众所周知，几乎所有图都可以通过一种简单的组合算法进行规范化处理，这种算法被称为“颜色细化”（color refinement），也称为一维Weisfeiler–Leman算法。该算法以很高的概率为随机输入图中的每个顶点分配一个唯一的标签，因此仅适用于非对称图。然而，当输入图具有高度对称性时，组合细化技术的有效性就成为一个值得关注的问题。我们证明了颜色细化与顶点个性化处理的结合可以为几乎所有循环有向图（即循环群的Cayley有向图）生成规范的标签。这一结果首次证明了组合细化算法在顶点传递图类中的良好平均性能。值得注意的是，我们甚至不需要使用颜色细化算法的全部功能。我们展示了只需计算从某个顶点出发到其他顶点的各种长度路径的数量，就可以得到该顶点的规范标签。我们的分析还表明，几乎所有循环图都满足Tinhofer的定义，即它们的分数自同构多面体是整数型的。最后，我们展示了可以使用更强大的二维Weisfeiler–Leman算法为几乎所有循环图构建规范的Cayley表示。

---

---

脚注

*

本文的初步版本曾在WALCOM’24会议上发表，该会议是第18届国际算法与计算会议及研讨会[45]。

#

作者目前从乌克兰利沃夫的IAPMM休假中。

---