Skew Spectra of Oriented Graphs

Abstract

An oriented graph $G^{\sigma}$ is a simple undirected graph $G$ with an orientation $\sigma$, which assigns to each edge a direction so that $G^{\sigma}$ becomes a directed graph. $G$ is called the underlying graph of $G^{\sigma}$, and we denote by $Sp(G)$ the adjacency spectrum of $G$. Skew-adjacency matrix $S( G^{\sigma} )$ of $G^{\sigma}$ is introduced, and its spectrum $Sp_S( G^{\sigma} )$ is called the skew-spectrum of $G^{\sigma}$. The relationship between $Sp_S( G^{\sigma} )$ and $Sp(G)$ is studied. In particular, we prove that (i) $Sp_S( G^{\sigma} ) = {\bf i} Sp(G)$ for some orientation $\sigma$ if and only if $G$ is bipartite, (ii) $Sp_S(G^{\sigma}) = {\bf i} Sp(G)$ for any orientation $\sigma$ if and only if $G$ is a forest, where ${\bf i}=\sqrt{-1}$.