The Weisfeiler-Leman Algorithm and Recognition of Graph Properties
| Autor: | Fuhlbrück, Frank, Köbler, Johannes, Ponomarenko, Ilia, Verbitsky, Oleg |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 30 pages, 2 figures. This paper supersedes Section 5 in the first version of arXiv:2002.04590. The 3rd version is a thorough revision of the paper |
| Databáze: | arXiv |
| Externí odkaz: |
|