Graph homomorphism counts reveal structure of graphs with simple spectrum
Distinguishing graphs with simple spectrum by homomorphism counts
Discrete Mathematics
Summary
This paper looks at how counting specific patterns called graph homomorphisms can tell apart certain kinds of graphs whose shapes are linked to simple spectra, a concept from their connection structure. The authors show that to distinguish all such graphs, the counting must come from very complex graph classes with particular properties. They also find relationships between these pattern counts and algebraic properties of graphs’ adjacency matrices, extending understanding of how graph structure relates to these counts. Their work provides new ways to see when two graphs can or cannot be told apart using these counting methods.
What this means in practice
- •For graph algorithm designers: Know when homomorphism counts from restricted graph classes suffice to distinguish graphs with simple spectrum, guiding efficient graph isomorphism testing strategies.
- •For network analysts: Use subcubic homomorphism counts to identify or classify networks that correspond to adjacency matrices with low kernel dimension, improving network comparison methods.
A theory result. No direct application yet.
Authors
Takanori Maehara
Abstract
We study which graph classes determine every graph with simple spectrum up to isomorphism by homomorphism counts from their members. We show that such a class has unbounded treewidth and Euler genus and contains a graph with the complete graph on seven vertices as a minor. To prove these conditions, we construct pairs of non-isomorphic cospectral graphs with simple spectrum, each bipartite, nonsingular and of maximum degree at most six. The construction attaches rooted trees to Cai-Furer-Immerman graphs and preserves homomorphism indistinguishability over every minor-closed class. We then prove that subcubic homomorphism counts determine every graph whose adjacency matrix has kernel dimension at most one. This extends the known result for nonsingular graphs and applies to all graphs with simple spectrum. We also prove that two graphs have the same subcubic homomorphism counts if and only if they have the same number of vertices and there is a bijective linear isometry between the images of their adjacency matrices that intertwines the adjacency operators and preserves the coordinatewise trilinear forms. Finally, we prove that homomorphism counts from the single-vertex graph and from subdivisions of any sequence of connected cubic graphs have the same distinguishing power as subcubic homomorphism counts if every complete graph is a minor of some member of the sequence.