New arithmetic invariants for cospectral graphs

Yizhe Ji, Quanyu Tang, Wei Wang, Hao Zhang

Published 2024-11-03Version 1

An invariant for cospectral graphs is a property shared by all cospectral graphs. In this paper, we present three new invariants for cospectral graphs, characterized by their arithmetic nature and apparent novelty. Specifically, let $G$ and $H$ be two graphs with adjacency matrices $A(G)$ and $A(H)$, respectively. We show, among other results, that if $G$ and $H$ are cospectral, then $e^{\rm T}A(G)^me\equiv e^{\rm T}A(H)^m e~({\rm mod}~4)$ for any integer $m\geq 0$, where $e$ is the all-one vector. As a simple consequence, we demonstrate that under certain conditions, every graph cospectral with $G$ is determined by its generalized spectrum.