Canonization of a random circulant graph by counting walks
| Autor: | Verbitsky, Oleg, Zhukovskii, Maksim |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | It is well known that almost all graphs are canonizable by a simple combinatorial routine known as color refinement. With high probability, this method assigns a unique label to each vertex of a random input graph and, hence, it is applicable only to asymmetric graphs. The strength of combinatorial refinement techniques becomes a subtle issue if the input graphs are highly symmetric. We prove that the combination of color refinement with vertex individualization produces a canonical labeling for almost all circulant digraphs (Cayley digraphs of a cyclic group). To our best knowledge, this is the first application of combinatorial refinement in the realm of vertex-transitive graphs. Remarkably, we do not even need the full power of the color refinement algorithm. We show that the canonical label of a vertex $v$ can be obtained just by counting walks of each length from $v$ to an individualized vertex. Our analysis also implies that almost all circulant graphs are canonizable by Tinhofer's canonization procedure. Finally, we show that a canonical Cayley representation can be constructed for almost all circulant graphs by the 2-dimensional Weisfeiler-Leman algorithm. Comment: 26 pages. A preliminary version of this paper appeared in the Proceedings of the 18th International Conference and Workshops on Algorithms and Computation (WALCOM'24), published in Lecture Notes in Computer Science Vol. 14549, Springer 2024. Sections 6 and 7 are new |
| Databáze: | arXiv |
| Externí odkaz: |
|