Skew Spectra of Oriented Bipartite Graphs
Open Access
- 14 October 2013
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 20 (4) , P18
Abstract
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 D. Cui and Y. Hou [D. Cui, Y. Hou, On the skew spectra of Cartesian products of graphs, Electronic J. Combin. 20(2):#P19, 2013]: 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 $Sp_S(G^{\phi})$ and $Sp(G)$ denote respectively the skew spectrum of $G^{\phi}$ and the spectrum of $G.$ Then $Sp_S(G^{\phi}) = {\bf{i}} 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.
Keywords
This publication has 7 references indexed in Scilit:
- 4-Regular oriented graphs with optimum skew energyLinear Algebra and its Applications, 2013
- Skew-adjacency matrices of graphsLinear Algebra and its Applications, 2012
- 3-Regular digraphs with optimum skew energyLinear Algebra and its Applications, 2012
- On the skew energy of orientations of hypercubesLinear Algebra and its Applications, 2011
- Characteristic Polynomials of Skew-Adjacency Matrices of Oriented GraphsThe Electronic Journal of Combinatorics, 2011
- The skew energy of a digraphLinear Algebra and its Applications, 2010
- Skew Spectra of Oriented GraphsThe Electronic Journal of Combinatorics, 2009