Name
Abstract | ||
|---|---|---|
The k-dimensional Weisfeiler-Leman algorithm is a powerful tool in graph isomorphism testing. For an input graph G, the algorithm determines a canonical coloring of s-tuples of vertices of G for each s between 1 and k. We say that a numerical parameter of s-tuples is k-WL-invariant if it is determined by the tuple color. As an application of Dvorak's result on k-WL-invariance of homomorphism counts in the case of k = 2, we spot some non-obvious regularity properties of strongly regular graphs and related graph families. For example, if G is a strongly regular graph, then the number of 7-paths between vertices x and y in G depends only on whether or not x and y are adjacent (this is true also for shorter paths but no longer true for 8-paths). Likewise, the number of cycles of length 7 passing through a vertex x in G is the same for every x (where the length 7 is also optimal). (c) 2021 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.dam.2021.08.037 | DISCRETE APPLIED MATHEMATICS |
Keywords | DocType | Volume |
Strongly regular graphs, Distance-regular graphs, Subgraph and homomorphism counts, Weisfeiler-Leman algorithm, Constituent graphs of association schemes | Journal | 305 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fuhlbrück Frank | 1 | 0 | 0.34 |
| Johannes Köbler | 2 | 31 | 6.83 |
| Verbitsky Oleg | 3 | 0 | 0.34 |