Distinguishing graphs with simple spectrum by homomorphism counts
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.
Related
- Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth
- Penalizations of Two-Dimensional Simple Random Walk by Direction-Dependent Excursion Counts and Edge-Crossing Counts
- Range of Clique Counts in Graphs
- Distinguishing invariants of Cayley Graphs, Hamming graphs, and wreath product actions
- The Borel Distinguishing Number of Schreier Graphs
BibTeX
@misc{maehara2026distinguishing,
title = {{Distinguishing graphs with simple spectrum by homomorphism counts}},
author = {Takanori Maehara},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09042},
eprint = {2610.09042},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09042},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Distinguishing graphs with simple spectrum by homomorphism counts
AU - Takanori Maehara
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.09042
UR - https://arxiv.org/abs/2610.09042
AB - 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.
ER -