The Weisfeiler-Leman Algorithm and Recognition of Graph Properties

DOI10.1007/978-3-030-75242-2_17MaRDI QIDQ6340948arXivFDO

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

Publication date 18 May 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-75242-2_17

Mathematics Subject Classification ID

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

arXiv classification

cs.CCmath.CO

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.

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)