A New Sufficient Condition for Oriented Graphs Determined by Their Generalized Skew Spectra
Abstract
Characterizing graphs uniquely determined by their spectra (DS) is a core open problem in spectral graph theory. While this problem has been extensively investigated for simple undirected graphs, it remains relatively underexplored for oriented graphs. For a simple undirected graph G equipped with an orientation σ, the corresponding oriented graph Σ=(G,σ) is the digraph obtained by orienting each edge of G according to σ. An oriented graph Σ is said to be \emph{determined by its generalized skew spectrum} (DGSS) if every oriented graph sharing the same generalized skew spectrum is isomorphic to Σ. This paper develops a new sufficient criterion for recognizing DGSS controllable oriented graphs, which applies to a much broader family of graphs than previously known results. Let S be the skew-adjacency matrix of Σ, W(Σ)=[e,Se,…,Sn−1e], and dn the last invariant factor of W(Σ). For each odd prime p, we define the polynomial Φp(Σ;x)=gcd(χ(S;x),χ(S+J;x)) over the finite field 𝔽p, which is invariant under generalized skew cospectrality. By analyzing the square-free part of Φp(Σ;x) and the associated p-main polynomial, we establish a DGSS sufficient condition under the square-free assumption on dn. The proposed criterion allows higher p-nullity and recovers the square-free determinant criterion of Qiu, Wang and Wang~(2019) as a special case. We further provide illustrative examples to verify the wider applicability of our new condition and to highlight the role of the compatibility constraints on the irreducible factors of Φp(Σ;x).
Related
- A sufficient condition for the existence of solutions of singular linear-quadratic vector equations
- Necessary and sufficient condition for reciprocal polynomials to be monogenic
- A Necessary and Sufficient Condition for the Existence of Global Smooth Solutions to the One-Dimensional Inviscid Burgers-Vlasov System
- A Simple Necessary and Sufficient Condition for Yang--Baxter Integrability
- On the Quadrature Surface Free Boundary Problem on Riemannian Manifolds: Sufficient Condition of Existence
BibTeX
@misc{lin2026sufficient,
title = {{A New Sufficient Condition for Oriented Graphs Determined by Their Generalized Skew Spectra}},
author = {Limeng Lin and Wei Wang and Wei Wang and Hao Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03428},
eprint = {2609.03428},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03428},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - A New Sufficient Condition for Oriented Graphs Determined by Their Generalized Skew Spectra
AU - Limeng Lin
AU - Wei Wang
AU - Wei Wang
AU - Hao Zhang
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.03428
UR - https://arxiv.org/abs/2609.03428
AB - Characterizing graphs uniquely determined by their spectra (DS) is a core open problem in spectral graph theory. While this problem has been extensively investigated for simple undirected graphs, it remains relatively underexplored for oriented graphs. For a simple undirected graph G equipped with an orientation σ, the corresponding oriented graph Σ=(G,σ) is the digraph obtained by orienting each edge of G according to σ. An oriented graph Σ is said to be \emph{determined by its generalized skew spectrum} (DGSS) if every oriented graph sharing the same generalized skew spectrum is isomorphic to Σ. This paper develops a new sufficient criterion for recognizing DGSS controllable oriented graphs, which applies to a much broader family of graphs than previously known results. Let S be the skew-adjacency matrix of Σ, W(Σ)=[e,Se,…,S^n−1e], and d_n the last invariant factor of W(Σ). For each odd prime p, we define the polynomial Φ_p(Σ;x)=gcd(χ(S;x),χ(S+J;x)) over the finite field 𝔽_p, which is invariant under generalized skew cospectrality. By analyzing the square-free part of Φ_p(Σ;x) and the associated p-main polynomial, we establish a DGSS sufficient condition under the square-free assumption on d_n. The proposed criterion allows higher p-nullity and recovers the square-free determinant criterion of Qiu, Wang and Wang~(2019) as a special case. We further provide illustrative examples to verify the wider applicability of our new condition and to highlight the role of the compatibility constraints on the irreducible factors of Φ_p(Σ;x).
ER -