2025/12/08 by Akbari, Saieed, Aloni, Jonathan, Levit, Maxwell +2
Computer Science · Mathematics · #05C35 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Tensor decomposition and applications
paper · doi:10.48550/arxiv.2512.08049
openalex publication_date 2025/12/08 · openalex created_date 2025/12/11 · openalex updated_date 2026/07/28
The Hermitian adjacency matrices of digraphs based on the sixth root of unity were introduced in [B. Mohar, A new kind of Hermitian matrices for digraphs, Linear Alg. Appl. (2020)]. They appear to be the most natural choice for the spectral theory of digraphs. Undirected graphs have adjacency spectrum symmetric about 0 if and only if they are bipartite. The situation is more complex for the Hermitian spectra of digraphs. In this paper we study non-bipartite oriented graphs with symmetric Hermitian spectra. Our main result concerns the extremal problem of maximizing the density of spectrally symmetric oriented graphs. The maximum possible density is shown to be between 13/18 and 10/11. Furthermore, we give a necessary condition for an oriented graph to be spectrally symmetric based on the adjacency spectrum of the underlying graph. This allows us to show that line graphs of sufficiently dense graphs do not admit spectrally symmetric orientations. We also show how to construct infinite families of spectrally symmetric graphs using 1-sums.