Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/978-3-030-75242-2_17 | CIAC |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fuhlbrück Frank | 1 | 0 | 0.34 |
| Johannes Köbler | 2 | 580 | 46.51 |
| Ponomarenko Ilia | 3 | 0 | 0.34 |
| Oleg Verbitsky | 4 | 191 | 27.50 |