Skew spectra of oriented bipartite graphs (Q396938)

Summary: A graph \(G\) is said to have a parity-linked orientation \(\phi\) if every even cycle \(C_{2k}\) in \(G^{\phi}\) is evenly (resp. oddly) oriented whenever \(k\) is even (resp. odd). In this paper, this concept is used to provide an affirmative answer to the following conjecture of \textit{C. Denglan} and \textit{H. Yaoping} [Electron. J. Comb. 20, No. 2, Research Paper P19, 13 p. (2013; Zbl 1266.05132)]: Let \(G=G(X,Y)\) be a bipartite graph. Call the \(X\rightarrow Y\) orientation of \(G,\) the canonical orientation. Let \(\phi\) be any orientation of \(G\) and let \(\mathrm{Sp}_S(G^{\phi})\) and \(\mathrm{Sp}(G)\) denote respectively the skew spectrum of \(G^{\phi}\) and the spectrum of \(G.\) Then \(\mathrm{Sp}_S(G^{\phi}) = \mathbf{i} \mathrm{Sp}(G)\) if and only if \(\phi\) is switching-equivalent to the canonical orientation of \(G\). Using this result, we determine the switch for a special family of oriented hypercubes \(Q_d^{\phi}\), \(d\geq 1.\) Moreover, we give an orientation of the Cartesian product of a bipartite graph and a graph, and then determine the skew spectrum of the resulting oriented product graph, which generalizes a result of Cui and Hou. Further this can be used to construct new families of oriented graphs with maximum skew energy.