Local WL Invariance and Hidden Shades of Regularity
| Autor: | Fuhlbrück, Frank, Köbler, Johannes, Verbitsky, Oleg |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 Dvo\v{r}\'ak's result on $k$-WL-invariance of homomorphism counts, 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 paths of length 6 between vertices $x$ and $y$ in $G$ depends only on whether or not $x$ and $y$ are adjacent (and the length 6 is here optimal). Or, 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). Comment: 12 pages, 2 figures, 1 table. Section 5 of the preceding version is moved to arxiv:2005.08887 |
| Databáze: | arXiv |
| Externí odkaz: |
|