An Upper Bound on the Number of Generalized Cospectral Mates of Oriented Graphs

Abstract

This paper examines the spectral characterizations of oriented graphs. Let $\Sigma$ be an $n$-vertex oriented graph with skew-adjacency matrix $S$. Previous research mainly focused on self-converse oriented graphs, proposing arithmetic conditions for these graphs to be uniquely determined by their generalized skew-spectrum ($\mathrm{DGSS}$). However, self-converse graphs are extremely rare; this paper considers a more general class of oriented graphs ${\mathcal{G}}_n$ (not limited to self-converse graphs), consisting of all $n$-vertex oriented graphs $\Sigma$ such that $2^{-\lfloor \frac{n}{2}\rfloor }\det W(\Sigma )$ is an odd and square-free integer, where $W(\Sigma )=[e,Se,\dots ,S^{n-1}e]$ ($e$ is the all-one vector) is the skew-walk matrix of $\Sigma$. Given that $\Sigma$ is cospectral with its converse ${\Sigma }^{\mathrm{T}}$, there always exists a unique regular rational orthogonal $Q_0$ such that $Q_0^{\mathrm{T}}S{Q}_0=-S$. This study reveals that there exists a deep relationship between the level ${\ell }_0$ of $Q_0$ and the number of generalized cospectral mates of $\Sigma$. More precisely, we show, among others, that the maximum number of generalized cospectral mates of $\Sigma \in {\mathcal{G}}_n$ is at most $2^t-1$, where $t$ is the number of prime factors of ${\ell }_0$. Moreover, some numerical examples are also provided to demonstrate that the above upper bound is attainable. Finally, we also provide a criterion for the oriented graphs $\Sigma \in {\mathcal{G}}_n$ to be weakly determined by the generalized skew-spectrum ($\mathrm{WDGSS})$.