{"id":"arxiv/2611.05366","url":"https://arxiv.org/abs/2611.05366","tags":["math.CO","cs.DM"],"score":0,"title":"Transfer of Weisfeiler-Leman equivalence under graph operations","domain":"math.CO","source":"arxiv","authors":["Dmitriy Kunisky","Hamilton Sawczuk"],"reviews":0,"subject":"math.CO","summary":"The Weisfeiler-Leman algorithms WL(k) for $k\\ge1$ form a hierarchy of increasingly powerful tests for graph isomorphism. We study how the equivalence relations they induce on graphs transfer through a graph operation $Φ$: for a given $k$, what level of WL-equivalence between graphs $H_1$ and $H_2$ guarantees WL(k)-equivalence of graphs $Φ(H_1)$ and $Φ(H_2)$? We call the least such level the transfer parameter $τ_Φ(k)$ and determine it exactly for the line graph operation $Φ= L$: $τ_L(k)=2k+1$ for $k\\ge2$, while $τ_L(1)=1$. We also extend these results to the $(r,S)$-line graphs, which…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}