Showing cs.CCShow all
3 papers · 1 filter
cs.CC2025
Canonization of a random circulant graph by counting walks
Oleg Verbitsky, Maksim Zhukovskii
It is well known that almost all graphs are canonizable by a simple combinatorial routine known as color refinement, also referred to as the 1-dimensional Weisfeiler-Leman algorith…
cs.CC2025
On a Hierarchy of Spectral Invariants for Graphs
V. Arvind, Frank Fuhlbrück, Johannes Köbler +1
We consider a hierarchy of graph invariants that naturally extends the spectral invariants defined by Fürer (Lin. Alg. Appl. 2010) based on the angles formed by the set of standar…
cs.CC2024
On the Expressibility of the Reconstructional Color Refinement
V. Arvind, Johannes Köbler, Oleg Verbitsky
One of the most basic facts related to the famous Ulam reconstruction conjecture is that the connectedness of a graph can be determined by the deck of its vertex-deleted subgraphs,…