Transfer of Weisfeiler-Leman equivalence under graph operations
Abstract
The Weisfeiler-Leman algorithms WL(k) for k≥1 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 H1 and H2 guarantees WL(k)-equivalence of graphs Φ(H1) and Φ(H2)? 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≥2, while τL(1)=1. We also extend these results to the (r,S)-line graphs, which generalize the line graph from edges to r-cliques by connecting two cliques when their intersection size lies in a prescribed set S. For these operations we prove that τr,S(1)=r−1 for every S and, for certain choices of S, that τr,S(k)=rk+r−1 for k≥ r, and we bound the transfer parameter in the remaining range. Our upper bounds on transfer parameters follow from a treewidth analysis of diagrammatic expansions of homomorphism counts into Φ(H) as linear combinations of homomorphism counts into H. The matching lower bounds combine explicit constructions of witness graphs with the homomorphism-distinguishing closedness of graphs of bounded treewidth.
Related
- An infinite family of intransitive directed strongly regular graphs with rank 6 Weisfeiler--Leman closure
- Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width
- Temporal Exploration and Rendezvous via Weisfeiler-Leman Colorings
- Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
- Brauer graph algebras are closed under stable equivalence of Morita type
BibTeX
@misc{kunisky2026transfer,
title = {{Transfer of Weisfeiler-Leman equivalence under graph operations}},
author = {Dmitriy Kunisky and Hamilton Sawczuk},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05366},
eprint = {2611.05366},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05366},
}
RIS
TY - UNPB
TI - Transfer of Weisfeiler-Leman equivalence under graph operations
AU - Dmitriy Kunisky
AU - Hamilton Sawczuk
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05366
UR - https://arxiv.org/abs/2611.05366
AB - The Weisfeiler-Leman algorithms WL(k) for k≥1 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≥2, while τ_L(1)=1. We also extend these results to the (r,S)-line graphs, which generalize the line graph from edges to r-cliques by connecting two cliques when their intersection size lies in a prescribed set S. For these operations we prove that τ_r,S(1)=r−1 for every S and, for certain choices of S, that τ_r,S(k)=rk+r−1 for k≥ r, and we bound the transfer parameter in the remaining range. Our upper bounds on transfer parameters follow from a treewidth analysis of diagrammatic expansions of homomorphism counts into Φ(H) as linear combinations of homomorphism counts into H. The matching lower bounds combine explicit constructions of witness graphs with the homomorphism-distinguishing closedness of graphs of bounded treewidth.
ER -