2024/10/13 by Y. Chao, Wei Wang, Chao, Yiquan +3
Computer Science · Mathematics · #05C50 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph Theory and Algorithms #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2410.09811
openalex publication_date 2024/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Spectral characterizations of graphs is an important topic in spectral graph theory which has been studied extensively by researchers in recent years. The study of oriented graphs, however, has received less attention so far. In Qiu et al.~\citeQWW (Linear Algebra Appl. 622 (2021) 316-332), the authors gave an arithmetic criterion for an oriented graph to be determined by its generalized skew spectrum (DGSS for short). More precisely, let Σ be an n-vertex oriented graph with skew adjacency matrix S and W(Σ)=[e,Se,…,Sn-1e] be the walk-matrix of Σ, where e is the all-one vector. A theorem of Qiu et al.~\citeQWW shows that a self-converse oriented graph Σ is DGSS, provided that the Smith normal form of W(Σ) is \rm diag(1,…,1,2,…,2,2d), where d is an odd and square-free integer and the number of 1's appeared in the diagonal is precisely \lceil (n)/(2)\rceil. In this paper, we show that the above square-freeness assumptions on d can actually be removed, which significantly improves upon the above theorem. Our new ingredient is a key intermediate result, which is of independent interest: for a self-converse oriented graphs Σ and an odd prime p, if the rank of W(Σ) is n-1 over \mathbbFp, then the kernel of W(Σ)\rm T over \mathbbFp is anisotropic, i.e., v\rm Tv≠ 0 for any 0≠ v∈\rm ker W(Σ)\rm T over \mathbbFp.