论文标题
Weisfeiler-Leman算法和图形属性的识别
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties
论文作者
论文摘要
$ k $二维WEISFEILER-LEMAN算法（$ K $ -WL）是图同构测试中非常有用的组合工具。我们解决$ k $ -wl的适用性，以识别图形属性。令$ g $为带有$ n $顶点的输入图。我们表明，如果$ n $是主要的，那么从$ g $上的2-wl的输出以及$ g $的顶点个性化的副本上，可以直接地看到$ g $的顶点传递性。但是，如果$ n $排除在16中，则$ k $ -wl将无法区分$ n $顶点的顶点传播和非vertex传播图，只要$ k = o（\ sqrt n）$。获得了类似的结果，以识别弧光性。
The $k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) is a very useful combinatorial tool in graph isomorphism testing. We address the applicability of $k$-WL to recognition of graph properties. Let $G$ be an input graph with $n$ vertices. We show that, if $n$ is prime, then vertex-transitivity of $G$ can be seen in a straightforward way from the output of 2-WL on $G$ and on the vertex-individualized copies of $G$. However, if $n$ is divisible by 16, then $k$-WL is unable to distinguish between vertex-transitive and non-vertex-transitive graphs with $n$ vertices as long as $k=o(\sqrt n)$. Similar results are obtained for recognition of arc-transitivity.
