Transfer of Weisfeiler-Leman equivalence under graph operations
Source: arxiv.org/abs/2611.05366
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.05366
curl -X POST /api/v1/records/arxiv/2611.05366/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.05366/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'