The Weisfeiler-Leman Algorithm and Recognition of Graph Properties

DOI10.1007/978-3-030-75242-2_17zbMATH Open1517.05166arXiv2005.08887MaRDI QIDQ6340948FDOQ6340948

Oleg Verbitsky, Johannes Köbler, Frank Fuhlbrück, Ilya Ponomarenko

Publication date: 18 May 2020

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(sqrtn)$. Similar results are obtained for recognition of arc-transitivity.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Association schemes, strongly regular graphs (05E30)

This page was built for publication: The Weisfeiler-Leman Algorithm and Recognition of Graph Properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6340948)