\documentclass[12pt,A4paper]{article} \usepackage{e-jc} \usepackage{latexcad} \usepackage{amssymb} \begin{document} \newtheorem{Theorem}{Theorem}[section] \newtheorem{thm}[Theorem]{Theorem} \newtheorem{cor}[Theorem]{Corollary} \newtheorem{lem}[Theorem]{Lemma} \newtheorem{prop}[Theorem]{Proposition} \newtheorem{defn}[Theorem]{Definition} \newtheorem{rem}[Theorem]{Remark} \newtheorem{algm}[Theorem]{Algorithm} \newtheorem{conj}[Theorem]{Conjecture} \newtheorem{prob}[Theorem]{Problem} \newtheorem{exa}[Theorem]{Example} %\numberwithin{equation}{subsection} \def\dfrac#1#2{{\displaystyle{#1\over#2}}} \def\I{{\bf i}} \def\G{{G^{\sigma}}} \def\H{{H^{\tau}}} \def\Gr{\overrightarrow{G}} \def\Hr{\overrightarrow{H}} \def\Gl{\overleftarrow{G}} %\def\G{\overleftarrow{G}} \def\T{\overrightarrow{T}} \def\P{\overrightarrow{P}} \def\a{\lambda} \def\zm{\noindent{\bf Proof. }} %\def\ezm{\begin{flushright} \end{flushright} } \def\ezm{\framebox[0.2cm][l]{\bf}\vspace*{0.2cm} } \title{On the skew spectra of Cartesian products of graphs} \author{Denglan Cui\\ \small Department of Mathematics\\[-0.8ex] \small Hunan Normal University, Changsha, Hunan 410081, China\\ Yaoping Hou\thanks{Corresponding author: \texttt{yphou@hunnu.edu.cn}} \\ \small Department of Mathematics\\[-0.8ex] \small Hunan First Normal University, Changsha, Hunan 410205, China\\ } \date{\dateline{Nov 1, 2012}{,2013}{ , 2013}} \maketitle \vspace*{0.1cm} \begin{abstract} An oriented graph $\G$ is a simple undirected graph $G$ with an orientation $\sigma,$ which assigns to each edge of $G$ a direction so that $\G$ becomes a directed graph. $G$ is called the underlying graph of $\G$ and we denote by $S(\G) $ the skew-adjacency matrix of $\G$ and its spectrum $Sp(\G)$ is called the skew-spectrum of $\G.$ In this paper, the skew spectra of two orientations of the Cartesian product of two graphs are discussed. As applications, new families of oriented bipartite graphs $\G$ with $Sp(\G)=\I Sp(G) $ are given and the orientation of a product graph with maximum skew energy is obtained. \end{abstract} {\it AMS Mathematics Subject Classification(2000):} 05C20 \ 05C50\\ {\it Keywords:} Oriented graphs; Spectra; Skew spectra; Skew energy; Pfaffian orientation. \normalsize \section{ Introduction} \hskip\parindent All graphs in this paper are simple and finite. Let $G$ be a graph with $n$ vertices and $A(G)=(a_{i,j})$ the adjacency matrix of $G,$ where $a_{i,j}=a_{j,i}=1 $ if there is an edge $ij$ between vertices $ i $ and $j$ in $G$ (denoted by $i\sim j$), otherwise $a_{i,j}=a_{j,i}=0.$ The $n$ roots of the characteristic polynomial $P(G;x)=det(x I -A(G) )$ of $A(G) $ are said to be the eigenvalues of the graph $G.$ Since $A(G)$ is symmetric, all eigenvalues of $A(G)$ are real and we denote by $Sp(G)$ the adjacency spectrum of $G.$ Let $\sigma $ be an orientation of graph $G$, which assigns to each edge of $G$ a direction so that the induced graph $\G$ is directed graph. {\em The skew-adjacency matrix $S(\G)=(s_{i,j})$ }is a real skew symmetric matrix, where $s_{i,j}=1 $ and $ s_{j,i}=-1$ if $i\rightarrow j$ is an arc of $\G,$ otherwise $s_{i,j}=s_{j,i}=0.$ The {\em skew-spectrum $Sp(\G)$} of $\G$ is defined as the spectrum of $S(\G) .$ Note that $Sp(\G) $ consists of only purely imaginary eigenvalues because $S(\G)$ is a real skew symmetric matrix. Throughout this paper, we denote the path, cycle and complete graph on $n$ vertices by $P_n, C_n $ and $K_n,$ respectively. Note that $P_2=K_2.$ While there are many results on spectrum of the adjacency matrix on a graph, there are comparably fewer results on the skew-adjacency matrix of a graph. It is worthy to mention that the square of the number of perfect matchings of a Pfaffian graph $G$ is the determinant of the skew-adjacency matrix $S(\G)$, see \cite{lp88} and references therein. The concept of the energy of an undirected graph was defined as $${\cal E}(G)= \sum_{\a \in Sp(G)} |\a|,$$ which was introduced by Gutman. One may check the online bibliography maintained by Gutman available at http: www.sgt.pep.ufrj.br/home.arquivos/energyenerbib.pdf. Recently, the skew energy of an oriented graph $\G$ was introduced in \cite{abw10} by Adiga, Balakrishnan and Wasin So. It is defined as the energy of the matrix $S(\G),$ that is, $${\cal E}(\G)= \sum_{\a \I \in Sp(\G)} |\a|.$$ In \cite{abw10}, some basic facts of the skew energy are discussed and some open problems are proposed \cite{abw10}, such as the following Problems 1.1 and 1.2. \begin{prob} Find new families of oriented graphs $\G$ with ${\cal E}(\G)= {\cal E}(G).$\end{prob} In \cite{ss09}, Shader and So showed that $Sp(\G)=\I Sp(G) $ for {\em some } orientation $\sigma$ if and only if $G$ is bipartite and $Sp(\G)=\I Sp(G) $ for {\em any } orientation $\sigma$ of $G$ if and only if $G$ is acyclic. Combinatorial proofs of these results can be found in \cite{ht11}. Some new families of oriented graphs with $Sp(\G)=\I Sp(G) $ can also be found in \cite{ht11,tian11}. \begin{prob}Which $k$-regular graphs on $n$ vertices have an orientation $\sigma$ with $ {\cal E}(\G)= n\sqrt{k},$ or equivalently $S(G)^TS(G)=kI_n?$\end{prob} Given a graph $G, $ which orientations of $G$ have maximum skew energy? This is also an interesting problem. In \cite{abw10}, it is shown that $ {\cal E}(\G)\leq n\sqrt{\Delta},$ where $\Delta$ is the maximum degree of $G$. It follows that if $G$ is a $k$-regular graph and $\sigma$ is an orientation with skew energy $n\sqrt{k}$ then $\sigma$ must be an orientation of $G$ with maximum skew energy among all orientations of $G$. The problems above motivate our investigation of the skew spectra of oriented graphs. In Section 2 we will show that an oriented graph $\G $ of a bipartite graph $G$ has $Sp(\G)=\I Sp(G)$ if and only if the orientation $\sigma$ is even cycle oriented uniformly, and if orientations $\sigma$ and $\tau$ of $G$ and $H$ with $Sp(\G)=\I Sp(G)$ and $Sp(H^{\tau})= \I Sp(H),$ respectively, then $Sp(\G \Box {H^{\tau}})=\I Sp( G\Box H).$ The latter fact will provide new digraphs with $Sp(\G)=\I Sp(G)$ from known oriented graphs. Let $G$ be a $k$-regular graph and $\G$ be an oriented graph of $G$ with skew energy $n\sqrt{k}.$ In Section 3, we will obtain an oriented graph of $ P_2 \Box G$ with skew energy $2n \sqrt{k+1} $ and hence obtain an oriented graph of $ P_2 \Box G$ with the maximum skew energy among all orientations of $P_2\Box G$. Note that $P_2 \Box G$ is $(k+1)$-regular if $G$ is $k$-regular. For any positive integer $k\geq 3$, we give new families of $k$-regular oriented graphs on $n=2^{k-1}$ vertices which have the maximum skew energy $ {\cal E}(\G)=n\sqrt{k},$ or equivalently, $S^T(\G)S(\G)=kI_n$. If $T$ is a tree, then $Sp(T^{\sigma})=\I Sp(T)$ for any orientation $\sigma$ of $T$ and hence $ {\cal E}(T^{\sigma})= {\cal E}(T).$ In Section 3 we will also give an orientation of $P_2\Box T$ with the maximum skew energy among all orientations of $P_2 \Box T.$ \section{Oriented graphs with $Sp(\G)=\I Sp(G)$} \hskip\parindent Let $G$ be a graph. A {\em linear subgraph} $L$ of $G$ is a subgraph of $G$ in which each component is either an edge or a cycle. A linear subgraph $L$ of $G$ is {\em evenly linear} if $L$ contains no cycle with odd length. A {\em $k$-matching} ${\cal M}$ in $G$ is a disjoint union of $k$-edges. If $2k$ is the order of $G,$ then a $k$-matching of $G$ is called a {\em perfect matching} of $G.$ Let $G$ be a graph and $A(G)$ be its adjacency matrix. Then the characteristic polynomial of $G$ is $$P(G;x)=\det(xI- A)=\sum_{i=0}^n a_i x^{n-i}. \eqno{(2.1)}$$ Here $a_0(G)=1,a_1(G)=0,$ and $ -a_2(G)$ is the number of edges in $G.$ In general, we have \begin{thm}(\cite{cds80}) Let $G$ be a graph and let the characteristic polynomial of $A(G)$ be expressed as in (2.1). Then $$a_i= \sum_{L \in {\cal L}_i}(-1)^{p_1(L)}(-2)^{p_2(L)},\eqno{(2.2)}$$ where $ {\cal L}_i$ denotes the set of all linear subgraphs $L$ of $G$ with $i$ vertices, $p_1(L)$ is the number of components of order 2 in $L$ and $p_2(L)$ is the number of cycles in $L.$ \end{thm} If $G$ is bipartite, then $a_i=0$ for all odd $i,$ and $$P(G;x)=\sum_{i=0}^{\lfloor \frac n2 \rfloor} (-1)^ib_{2i}(G) x^{n-2i} , \eqno{(2.3)}$$ where all $b_{2i}=(-1)^ia_{2i}$ are nonnegative. Let $C$ be an undirected even cycle of $\G.$ Now regardless of which of the possible routing around $C$ is chosen, if $C$ contains an even number of oriented arcs whose orientation agrees with the routing, then $C$ also contains an even number of arcs whose orientation is opposite to the routing. Hence the following definition is independent of the routing chosen. If $C$ is any undirected even cycle of $\G,$ we say $C$ is {\em evenly oriented relative to $\G$ } if it has an even number of arcs oriented in the direction of the routing. Otherwise $C$ is {\em oddly oriented.} Let $\sigma$ be an orientation of $G$ and $S(\G)$ be the skew-adjacency matrix of $\G.$ Denote the characteristic polynomial of $S(\G)$ by $$ P(\G; x)=\det(xI -S)=\sum_{i=0}^n c_i x^{n-i}. \eqno{(2.4)}$$ Then (i) $c_0=1,$ (ii) $c_2$ is the number of edges of $G,$ (iii) $ c_i\geq 0 $ for all $i$ and (iv) $c_i = 0$ for all odd $i$ since the determinant of any skew symmetric matrix is 0 if its order is odd. In general, we have \begin{thm} \cite{ht11} Let $\sigma$ be an orientation of $G.$ Then $$c_{i}= \sum_{L \in {\cal EL}_{i}}(-2)^{p_e(L)}2^{p_o(L)}, \eqno{(2.5)} $$ where ${\cal EL}_{i}$ is the set of all evenly linear subgraphs of $\G$ with $i$ vertices, $p_e(L)$ is the number of evenly oriented cycles of $L$ relative to $\G$ and $p_o(L)$ is the number of oddly oriented cycles of $L$ relative to $\G$ . In particular, $c_i=0$ if $i$ is odd. \end{thm} Let $\sigma$ be an orientation of $G$ and the characteristic polynomials of $A(G)$ and $S(\G)$ be expressed as in (2.1) and (2.4), respectively. Because the roots of $P(\G;x)$ are pure imaginary and occur in complex conjugate pairs, while the roots of $P(G; x)$ are all real, it follows that $Sp(\G)=\I Sp(G)$ if and only if $ P(G;x) = \sum_{i=0}^{n}a_ix^{n-i}=x^{n-2r}\prod_{i=1}^r(x^2-\lambda_i^2)$ and $ P(\G;x) = \sum_{i=0}^{n}c_ix^{n-i}=x^{n-2r}\prod_{i=1}^r(x^2+\lambda_i^2)$ for some non-zero real numbers $\a_1,\a_2,...,\a_{r}$ if and only if $$a_{2i}=(-1)^ic_{2i},\;\; a_{2i+1}=c_{2i+1}=0,\eqno({2.6}) $$ where $ i=0,1,...,\lfloor \frac n2 \rfloor.$ The following result was first obtained in \cite{ss09} by Shader and So. \begin{thm}\label{bip} A graph $G$ is bipartite if and only if there is an orientation $\sigma$ of $G$ such that $Sp(\G)=\I Sp(G).$ \end{thm} For which orientations $\sigma$ of a bipartite graph, do we have $Sp(\G)=\I Sp(G)$? This may be an interesting problem. We need a definition to do this. Let $\sigma$ be an orientation of a graph $G. $ An even cycle $C_{2\ell}$ is said to be {\em oriented uniformly } if $C_{2\ell}$ is oddly (resp., evenly) oriented relative to $\G$ when $\ell$ is odd (resp., even). \begin{thm}\label{unif} Let $G$ be a bipartite graph and $\sigma$ be an orientation of $G.$ Then $Sp(\G)=\I Sp(G)$ if and only if every even cycle is oriented uniformly in $\G.$ \end{thm} \zm Since $G$ is bipartite, all cycles in $G$ are even and all linear subgraphs are even. Then $a_{2i+1}=0$ for all $i.$ (Sufficiency) Since every even cycle is oriented uniformly, for every cycle $C_{2\ell}$ with length $2\ell,$ $C_{2\ell}$ is evenly oriented relative to $\G$ if and only if $\ell$ is even. Thus $(-1)^{p_e(C_{2\ell})}=(-1)^{\ell+1}.$ By Eqs (2.2) and (2.5), we have $$(-1)^ia_{2i}=m(G,i)+\sum_{L \in {\cal CL}_{2i} }(-1)^{p_1(L)+i}(-2)^{p_2(L)}, \eqno({2.7})$$ $$c_{2i}=m(G,i)+\sum_{L \in {\cal CL}_{2i} }(-2)^{p_e(L)}2^{p_o(L)}, \eqno({2.8})$$ where $m(G,i)$ is the number of matchings with $i$ edges and ${\cal CL}_{2i}$ is the set of all linear subgraphs with $2i$ vertices of $G$ and with at least one cycle. For a linear subgraph $L \in {\cal CL}_{2i} $ of $G,$ assume that $L$ contains the cycles $C_{2\ell_1},...,C_{2\ell_{p_2}}. $ Then the number of components of $L$ that are single edges is $p_1(L)= i-\sum_{j=1}^{p_2(L)} \ell_j.$ Hence $(-1)^{p_1(L)+i}=(-1)^{\sum_{j=1}^{p_2(L)} \ell_j }.$ Therefore $L$ contributes $$(-1)^{\ell_1+1}\cdots (-1)^{\ell_{p_2}+1} 2^{p_2(L)}=(-1)^{p_1(L)+i}(-2)^{p_2(L)}$$ in $c_{2i}.$ Thus $(-1)^ia_{2i}= c_{2i}$ by Eqs. (2.7) and (2.8) and the sufficiency is proved. (Necessity) If there is an even cycle of $G$ that is not oriented uniformly in $\G$, then choose a shortest cycle $C_{2\ell}$ with length $2\ell$ such that $C_{2\ell}$ is not oriented uniformly, that is, $C_{2\ell}$ is oddly oriented in $\G$ if $\ell $ is even, and evenly oriented if $\ell$ is odd. Assume that there are $r$ cycles with length $2\ell$ such that they are not oriented uniformly, and let ${\cal UCL}_{2\ell}$ denote the set of all even linear subgraphs with $2\ell$ vertices of $G$ and all even cycles that are oriented uniformly. Thus, we have $$(-1)^{\ell}a_{2\ell}=m(G,\ell)+ r(-1)^{\ell}(-2)+\sum_{L \in {{\cal UCL}_{2\ell}} }(-1)^{p_1(L)+\ell}(-2)^{p_2(L)},$$ $$c_{2\ell}=m(G,l)+ r(-1)^{\ell} 2+\sum_{L \in {{\cal UCL}_{2\ell}}} (-2)^{p_e(L)}2^{p_o(L)}.$$ By the choice of $C_{2\ell}$ and the proof of the necessity, $\sum_{L \in {{\cal UCL}_{2\ell}} }(-1)^{p_1(L)+\ell}(-2)^{p_2(L)}=\sum_{L \in {{\cal UCL}_{2\ell}}} (-2)^{p_e(L)}2^{p_o(L)}.$ Thus $(-1)^{\ell}a_{2\ell}\not=c_{2\ell}$ and hence $Sp(\G)\not=\I Sp(G)$ by Eq. (2.6). \ezm Let $G$ and $H$ be graphs with $n_1$ and $n_2$ vertices, respectively. The Cartesian product $G \Box H $ of $G$ and $H$ is a graph with vertex set $V(G) \Box V(H)$ and there exists an edge between $(u_1,v_1)$ and $(u_2,v_2)$ if and only if $u_1=u_2$ and $ v_1v_2$ is an edge of $H,$ or $v_1=v_2$ and $ u_1u_2$ is an edge of $G.$ Orientations $\sigma$ and $\tau$ of graphs $G$ and $H $ will give an orientation of $G \Box H$ in a natural way and this gives the Cartesian product $\G \Box \H $ of $\G$ and $\H,$ a directed graph with vertex set $V(G) \Box V(H)$ and there exists an arc from $(u_1,v_1)$ to $(u_2,v_2)$ if and only if $u_1=u_2$ and $ (v_1,v_2)$ is an arc of $\H,$ or $v_1=v_2$ and $ (u_1,u_2)$ is an arc of $\G.$ It is easy to see that $\G \Box \H $ is an oriented graph of $G\Box H.$ With suitable labeling of vertices of $ G\Box H, $ one can obtain the skew adjacency matrix of $\G\Box \H$ as $ I_{n_1} \otimes S(H^{\tau}) + S(\G) \otimes I_{n_2} .$ Thus, the skew eigenvalues of $\G\Box \H$ are $ \lambda (\G) + \mu(\H) ,\;\; \lambda (\G) \in Sp(\G),\mu(\H) \in Sp(\H).$ \begin{thm} Let $\G$ and $\H$ be oriented graphs with $Sp(\G)= \I Sp(G)$ and $ Sp(\H)=\I Sp(H) ,$ respectively. Then $Sp( \G\Box \H)= \I Sp(G \Box H).$ \end{thm} \zm Let the eigenvalues of $G$ and $H$ be $\lambda_1, \cdots, \lambda_{n_1}$ and $\mu_1, \cdots, \mu_{n_2},$ respectively. Then the eigenvalues of $G \Box H$ are $\lambda_i+\mu _j, i=1,\cdots, n_1, j=1,\cdots,n_2.$ Since $Sp(\G)= \I Sp(G)$ and $ Sp(\H)=\I Sp(H) ,$ $Sp(\G)=\{\lambda_1 \I, \cdots, \lambda_{n_1} \I \}$ and $ Sp(\H)=\{\mu_1 \I, \cdots, \mu_{n_2} \I\}$. Thus $Sp(\G\Box \H)=\{\lambda_i \I+\mu _j \I, i=1,\cdots, n_1, j=1,\cdots,n_2\}=\I Sp(G\Box H).$ \ezm. \begin{exa}\label{excube3} In \cite{tian11}, an oriented hypercube $\overrightarrow{{\cal H}_d}$ satisfying $Sp( \overrightarrow{{\cal H}_d})= \I Sp(H_d)$ is given. In fact, this orientation gives the Cartesian product of the directed graphs $\overrightarrow{{\cal H}_d}=\overrightarrow{K_2} \Box \overrightarrow{{\cal H}_{d-1}}$ and $\overrightarrow{{\cal H}_1}=\overrightarrow{K_2}.$ See Fig. \ref{cube3} \end{exa} \unitlength=1.2mm \begin{figure}[hp] \begin{picture}(114,36) \thinlines \drawthickdot{32.0}{26.0} \drawthickdot{32.0}{12.0} \drawthickdot{52.0}{26.0} \drawthickdot{66.0}{26.0} \drawthickdot{52.0}{12.0} \drawthickdot{66.0}{12.0} \drawthickdot{94.0}{30.0} \drawthickdot{88.0}{24.0} \drawthickdot{108.0}{30.0} \drawthickdot{94.0}{16.0} \drawthickdot{88.0}{10.0} \drawthickdot{108.0}{16.0} \drawthickdot{102.0}{10.0} \drawthickdot{102.0}{24.0} \drawpath{32.0}{26.0}{32.0}{12.0} \drawpath{52.0}{26.0}{52.0}{12.0} \drawpath{66.0}{26.0}{66.0}{12.0} \drawpath{66.0}{12.0}{52.0}{12.0} \drawpath{52.0}{26.0}{66.0}{26.0} \drawpath{94.0}{30.0}{108.0}{30.0} \drawpath{108.0}{30.0}{102.0}{24.0} \drawpath{102.0}{24.0}{88.0}{24.0} \drawpath{88.0}{24.0}{94.0}{30.0} \drawpath{94.0}{30.0}{94.0}{16.0} \drawpath{94.0}{16.0}{108.0}{16.0} \drawpath{108.0}{16.0}{102.0}{10.0} \drawpath{102.0}{10.0}{88.0}{10.0} \drawpath{88.0}{10.0}{94.0}{16.0} \drawpath{88.0}{24.0}{88.0}{10.0} \drawpath{102.0}{24.0}{102.0}{10.0} \drawpath{108.0}{30.0}{108.0}{16.0} \drawvector{32.0}{26.0}{10.0}{0}{-1} \drawvector{52.0}{26.0}{8.0}{0}{-1} \drawvector{66.0}{26.0}{8.0}{0}{-1} \drawvector{52.0}{26.0}{8.0}{1}{0} \drawvector{52.0}{12.0}{10.0}{1}{0} \drawvector{94.0}{30.0}{8.0}{1}{0} \drawvector{88.0}{24.0}{10.0}{1}{0} \drawvector{88.0}{24.0}{4.0}{1}{1} \drawvector{102.0}{24.0}{4.0}{1}{1} \drawvector{88.0}{24.0}{10.0}{0}{-1} \drawvector{94.0}{30.0}{10.0}{0}{-1} \drawpath{102.0}{24.0}{102.0}{18.0} \drawvector{102.0}{24.0}{8.0}{0}{-1} \drawvector{108.0}{30.0}{10.0}{0}{-1} \drawvector{88.0}{10.0}{10.0}{1}{0} \drawvector{102.0}{10.0}{4.0}{1}{1} \drawvector{88.0}{10.0}{4.0}{1}{1} \drawvector{94.0}{16.0}{6.0}{1}{0} \drawcenteredtext{32.0}{6.0}{$\overrightarrow{{\cal H}_1}$} \drawcenteredtext{60.0}{6.0}{$\overrightarrow{{\cal H}_2}$} \drawcenteredtext{94.0}{6.0}{$\overrightarrow{{\cal H}_3}$} \end{picture} %\input{cube3.tex} \caption{The first three oriented hypercubes in Example 2.6.}\label{cube3} \end{figure} Let $\sigma$ be an orientation of a graph $G$. Let $W$ be a subset of $V(G)$ and $\overline{W}=V(G)\setminus W$. The orientation $\tau$ of $G $ obtained from $\sigma$ by reversing the orientations of all arcs between $\overline{W}$ and $W$ is said to be obtained from $\G$ by a switching with respect to $W$. If $G^{\tau}$ is obtained from $\G$ by a switching with respect to $W,$ then $S(G^{\tau})=PS(\G)P$ for a diagonal signed matrix $P=(p_{ij}),$ where $p_{ii}=-1$ if $i \in W,$ 1 otherwise. Moreover, two oriented graphs $\G$ and $G^{\tau}$ of $G$ are said to be switching-equivalent if $G^{\tau}$ can be obtained from $\G$ by a switching. The following result is proved in \cite{abw10}. \begin{lem} (\cite{abw10}) Let $\sigma$ and $ \tau $ be orientations of $G.$ If $\G$ and $G^{\tau}$ are switching-equivalent then $Sp(\G)=Sp(G^{\tau})$ and ${\cal E} (\G) = {\cal E}(G^{\tau})$.\label{switch}\end{lem} Let $G$ be a bipartite graph with the bipartition $V(G)=X\cup Y$. We call an orientation $\sigma$ of $G$ {\em elementary} if it assigns each edge of $G$ the direction from $X$ to $Y.$ For the elementary orientation $\sigma$ of a bipartite graph $G,$ $Sp(\G)=\I Sp(G)$ by Theorem 2.2 in \cite{ss09}. In \cite{tian11}, it is claimed that the oriented graph $\overrightarrow{{\cal H}_d}$ is non-isomorphic to the elementary oriented graph of $H_d.$ But we have \begin{prop} The orientation $\sigma$ of $\overrightarrow{{\cal H}_d}$ of $H_d$ in Example \ref{excube3} is switching-equivalent to the elementary orientation of $H_d.$ \end{prop} \zm We prove the proposition by induction on $d$. The proposition holds for $d=1$ and $d=2 $ clearly. Now we suppose that $\overrightarrow{{\cal H}_{d-1}}$ is switching-equivalent to the elementary orientation of $H_{d-1}$ with the bipartition $X\cup Y$. Then the vertex set of $H_d$ is $X\cup Y \cup X' \cup Y' $ and $\overrightarrow{{\cal H}_d}$ is depicted in Fig. \ref{bicube}. Then $\overrightarrow{{\cal H}_d}$ is switching-equivalent to the elementary orientation of $H_d$ by switching with respect to $Y'.$ \ezm \unitlength=0.9mm \begin{figure}[hp] \begin{picture}(170,54) \thinlines \drawcircle{12.0}{42.0}{16.0}{} \drawcircle{12.0}{16.0}{0.0}{} \drawcircle{12.0}{20.0}{16.0}{} \drawcircle{54.0}{42.0}{16.0}{} \drawcircle{54.0}{20.0}{16.0}{} \drawcircle{90.0}{42.0}{16.0}{} \drawcircle{90.0}{20.0}{16.0}{} \drawvector{8.0}{34.0}{6.0}{0}{-1} \drawvector{16.0}{34.0}{6.0}{0}{-1} \drawvector{50.0}{34.0}{6.0}{0}{-1} \drawvector{54.0}{34.0}{6.0}{0}{-1} \drawvector{58.0}{34.0}{6.0}{0}{-1} \drawvector{86.0}{34.0}{6.0}{0}{-1} \drawvector{90.0}{34.0}{6.0}{0}{-1} \drawvector{94.0}{34.0}{6.0}{0}{-1} \drawvector{60.0}{48.0}{24.0}{1}{0} \drawvector{62.0}{44.0}{20.0}{1}{0} \drawvector{62.0}{40.0}{20.0}{1}{0} \drawvector{62.0}{22.0}{20.0}{1}{0} \drawvector{62.0}{18.0}{20.0}{1}{0} \drawvector{60.0}{14.0}{24.0}{1}{0} \drawcenteredtext{12.0}{42.0}{$X$} \drawcenteredtext{12.0}{20.0}{$Y$} \drawcenteredtext{54.0}{40.0}{$X$} \drawcenteredtext{54.0}{20.0}{$Y$} \drawcenteredtext{90.0}{42.0}{$X'$} \drawcenteredtext{90.0}{20.0}{$Y'$} \drawcenteredtext{12.0}{6.0}{$\Hr_{d-1}$} \drawcenteredtext{72.0}{8.0}{$\Hr_d$} \drawcircle{126.0}{42.0}{16.0}{} \drawcircle{158.0}{42.0}{16.0}{} \drawcircle{126.0}{20.0}{16.0}{} \drawcircle{158.0}{20.0}{16.0}{} \drawcenteredtext{126.0}{42.0}{$X$} \drawcenteredtext{126.0}{18.0}{$Y$} \drawcenteredtext{158.0}{42.0}{$X'$} \drawcenteredtext{158.0}{18.0}{$Y'$} \drawvector{122.0}{34.0}{6.0}{0}{-1} \drawvector{126.0}{34.0}{6.0}{0}{-1} \drawvector{130.0}{34.0}{6.0}{0}{-1} \drawvector{132.0}{48.0}{20.0}{1}{0} \drawvector{134.0}{44.0}{16.0}{1}{0} \drawvector{134.0}{40.0}{16.0}{1}{0} \drawvector{160.0}{28.0}{6.0}{0}{1} \drawvector{164.0}{26.0}{10.0}{0}{1} \drawvector{156.0}{28.0}{6.0}{0}{1} \drawvector{150.0}{22.0}{16.0}{-1}{0} \drawvector{150.0}{18.0}{16.0}{-1}{0} \drawvector{152.0}{14.0}{20.0}{-1}{0} \drawvector{12.0}{34.0}{6.0}{0}{-1} \drawcenteredtext{142.0}{6.0}{A switching of $\Hr_d$} \end{picture} %\input{bicube} \caption{ An orientation and a switching of $H_d$ }\label{bicube} \end{figure} We pose the following conjecture. \begin{conj} Let $G=G(X,Y)$ be a bipartite graph and let $\sigma$ be an orientation of $G$. Then $Sp(\G)=\I Sp(G)$ if and only if $\sigma$ is switching equivalent to the elementary orientation of $G.$ \end{conj} \section{An orientation of $P_m \Box G$ with the maximum skew energy} \hskip\parindent In this section, first, we will define an orientation of the product graph $ P_m \Box G $ and determine its skew spectrum. As applications of this orientation, we then give new families of oriented graphs with the maximum skew energy. Let $\Gr$ be any orientation of $G$ and let $\Gl$ be the converse of $\Gr$ which is the oriented graph obtained from $\Gr$ by reversing the orientation of each arc. We define an oriented graph $(P_m \Box G)^o$ of $ P_m \Box G $ as follows. Let $V(G)=\{v_1,v_2,\cdots, v_n\}$ be the vertex set of $G.$ Take $m$ copies of $G,$ denoted by $G_1,G_2,..., G_m,$ where $V(G_i)=\{v_1^{(i)},v_2^{(i)},\cdots, v_n^{(i)}\}$ is the vertex set of $G_i, i=1,2,...,m.$ If we add the set of edges $\{v_j^{(i)}v_j^{(i+1)}| 1\leq j \leq n\}$ between every pair of graphs $G_i$ and $G_{i+1}$, for $i=1,2,...,m-1,$ then the resulting graph is $P_m \Box G.$ We define the oriented graph $\Gr_i$ of $G_i$ in $P_m \Box G$ to be $\Gr$ if $i$ is odd and the converse $\Gl$ otherwise, and the direction of edges of the form $v_j^{(i)}v_j^{(i+1)} (1\leq j \leq n, 1\leq i \leq m-1)$ in $P_m \Box G$ are from $v_j^{(i)}$ to $v_j^{(i+1)}.$ Hence we obtain an oriented graph of $P_m \Box G,$ denoted by $(P_m \Box G)^o.$ See Figure \ref{prpath} below. \unitlength=1.2mm \begin{figure}[htbp]\label{prpath} \begin{picture}(126,22) \thinlines \drawoval{9.0}{11.0}{10.0}{14.0}{} \drawoval{35.0}{11.0}{10.0}{14.0}{} \drawoval{61.0}{11.0}{10.0}{14.0}{} \drawoval{89.0}{11.0}{10.0}{14.0}{} \drawoval{115.0}{11.0}{10.0}{14.0}{} \drawvector{14.0}{14.0}{16.0}{1}{0} \drawvector{14.0}{10.0}{16.0}{1}{0} \drawvector{14.0}{6.0}{16.0}{1}{0} \drawvector{40.0}{14.0}{16.0}{1}{0} \drawvector{40.0}{10.0}{16.0}{1}{0} \drawvector{40.0}{6.0}{16.0}{1}{0} \drawvector{94.0}{14.0}{16.0}{1}{0} \drawvector{94.0}{10.0}{16.0}{1}{0} \drawvector{94.0}{6.0}{16.0}{1}{0} \drawcenteredtext{8.0}{10.0}{$\Gr_1$} \drawcenteredtext{36.0}{10.0}{$\Gl_2$} \drawcenteredtext{60.0}{10.0}{$\Gr_3$} \drawdot{74.0}{10.0} \drawdot{76.0}{10.0} \drawdot{78.0}{10.0} \drawvector{66.0}{14.0}{6.0}{1}{0} \drawvector{66.0}{10.0}{6.0}{1}{0} \drawvector{66.0}{6.0}{6.0}{1}{0} \drawvector{80.0}{14.0}{4.0}{1}{0} \drawvector{80.0}{10.0}{4.0}{1}{0} \drawvector{80.0}{6.0}{4.0}{1}{0} \drawcenteredtext{90.0}{10.0}{$\Gr_{m-1}$} \drawcenteredtext{116.0}{10.0}{$\Gr_m$} \end{picture} %\input{prpath.tex} \caption{ The oriented graph $(P_m\Box G)^o$ of $P_m\Box G$} \end{figure} \begin{lem}\label{sing} Let $A$ and $B$ be real matrices and let $P,Q$ be orthogonal matrices. If $B=PAQ,$ then $A$ and $B$ have the same singular values. \end{lem} \zm The lemma follows immediately from $BB^T=(PAQ)(PAQ)^T=PAA^TP^T.$ \ezm \begin{lem}\label{sprod} Let $\sigma$ be an orientation of $G$ and let the skew eigenvalues of $\G$ be the non-zero values $\pm\lambda_1 \I,..., \pm\lambda_r \I $ and $n-2r$ 0's. Let the eigenvalues of the path $P_m$ be $\mu_1,\mu_2,...,\mu_m$. Then the skew eigenvalues of the oriented graph $ (P_m \Box G)^o $ are $ \pm\I \sqrt{\lambda_i^2 + \mu_j^2},\;\\ i=1,2,...,r,\; j=1,2,...,m,$ and $ \mu_j\I $ with multiplicities $n-2r, \; j=1,2,...,m.$ \end{lem} \zm With suitable labeling of the vertices of $ P_m\Box G, $ we can obtain that the skew adjacency matrix of $(P_m\Box G)^o$ is the following: $$ S((P_m\Box G)^o)=\left(\begin{array}{cccccc} S(\G)& I& 0&\cdots& 0 & 0\\ -I&-S(\G)& I& \cdots &0&0\\ 0&-I&S(\G)& \cdots& 0& 0\\ \vdots&\vdots&\vdots &\ddots & \vdots &\vdots\\ 0&0&0&\cdots& (-1)^{m-2}S(\G)&I\\ 0&0&0&\cdots& -I&(-1)^{m-1}S(\G)\\ \end{array} \right) $$ Now multiplying the first column, then the third and fourth row, then the fourth and fifth column, then the seventh and eighth row, etc.\ of the partition matrix $S((P_m\Box G)^o)$ by $-1,$ we obtain a matrix $$ M=\left(\begin{array}{cccccc} -S(\G)& I_n& 0&\cdots& 0 & 0\\ I_n&-S(\G)& I_n& \cdots &0&0\\ 0&I_n&-S(\G)& \cdots& 0& 0\\ \vdots&\vdots&\vdots &\ddots & \vdots &\vdots\\ 0&0&0&\cdots& -S(\G)&I_n\\ 0&0&0&\cdots& I_n&-S(\G)\\ \end{array} \right). $$ By Lemma \ref{sing}, $S((P_m\Box G)^o)$ and $M$ have the same singular values . If we denote by $A(P_m)$ the adjacency matrix of the path $P_m,$ that is, $$ A(P_m)=\left(\begin{array}{cccccc} 0& 1& 0&\cdots& 0 & 0\\ 1&0& 1& \cdots &0&0\\ 0&1&0& \cdots& 0& 0\\ \vdots&\vdots&\vdots &\ddots & \vdots &\vdots\\ 0&0&0&\cdots& 0&1\\ 0&0&0&\cdots& 1&0\\ \end{array} \right), $$ then $M= -I_m \otimes S(\G) + A(P_m)\otimes I_n. $ Note that $M^T=I_m \otimes S(\G) + A(P_m)\otimes I_n $ and $MM^T=-I_m \otimes S(\G)^2 + A(P_m)^2 \otimes I_n.$ Thus the eigenvalues of $MM^T$ are $\lambda(\G)^2 + \mu(P_m)^2,$ where $ \lambda(\G) \I \in Sp(\G)$ and $ \mu(P_m) \in Sp(P_m).$ Then the skew spectrum of $(P_m \Box G)^o $ follows. \ezm \begin{cor} Let $\sigma$ be an orientation of $G$ and the skew eigenvalues of $\G$ be non-zero $\lambda_1 \I,..., \lambda_r \I$ and $n-2r$ 0's. Then the skew eigenvalues of the oriented graph $(P_2 \Box G)^o $ are $\pm \I\sqrt{\lambda_i^2 + 1}, i=1,2,...,r,$ and $\pm \I $ with multiplicities $n-2r.$ \end{cor} As an application of Lemma \ref{sprod}, we can obtain some formula for the number of perfect matchings of a pfaffian graph. If the oriented graph $(P_m \Box G)^o $ is a Pfaffian then the number of perfect matchings of $P_m \Box G$ is the square root of the determinant of the skew adjacency matrix, and the determinant of a matrix is the product of its eigenvalues. See \cite{yanzhang03,zhangyan06} for more details. We recall the following result from \cite{abw10}. \begin{thm}\cite{abw10} Let $\sigma$ be an orientation of a graph $G$ of order $n.$ Then ${\cal E}(\G)\leq n\sqrt{\Delta}$ and equality holds if and only if $S(\G)^TS(\G)=\Delta I_n.$ \end{thm} From above theorem, it follows that if ${\cal E}(\G)= n\sqrt{\Delta}$ then $G$ must be $\Delta$-regular and $\sigma$ has the maximum skew energy among all orientations of $G.$ A natural question is posed in \cite{abw10}: Which $k$-regular graphs on $n$ vertices have orientations $\sigma$ with ${\cal E}(\G)= n\sqrt{k},$ or equivalently, $S(\G)^TS(\G)=kI_n$ ? Adiga et al.\ showed that a 1-regular graph with $n$ vertices has an orientation with $S(\G)^TS(\G)=I_n$ if and only if $n$ is even and $G$ is $\frac n2$ copies of $K_2,$ and a 2-regular graph with $n$ vertices has an orientation with $S(\G)^TS(\G)=2I_n$ if and only if $n$ is a multiple of 4 and $G$ is a union of $\frac n4$ copies of $C_4, $ see \cite{abw10}. Tian proved that there exists a $k$-regular graph with $n=2^k$ vertices having an orientation $\sigma$ with $S(\G)^TS(\G)=kI_n$ for all $k\geq 3.$ (See \cite{tian11} and Example \ref{2reg} below). The following Example \ref{3reg} provides a new class of $k$-regular graphs of order $n=2^{k-1}$ having an orientation $\sigma$ with $S(\G)^TS(\G)=kI_n$ for all $k\geq 3.$ \begin{thm} Let $\G$ be an oriented $k$-regular graph of $G$ on $n$ vertices with the maximum skew energy ${\cal E}(\G)= n\sqrt{k}.$ Then the oriented graph $(P_2 \Box G )^o$ of $P_2\Box G$ has the maximum skew energy ${\cal E}((P_2 \Box G )^o)= 2n\sqrt{k+1}.$ \end{thm} \zm Since $\G$ has the maximum skew energy ${\cal E}(\G)= n\sqrt{k},$ equivalently, $S(\G)^TS(\G)=kI_n,$ where $n$ is the number of vertices of $G.$ By a suitable labeling of the vertices of $P_2 \Box G$, the skew adjacency matrix of $(P_2\Box G)^o$ has the following form: $$ S((P_2\Box G )^o)= \left(\begin{array}{cc} S(\G) & I_n\\ -I_n & -S(\G)\end{array}\right).$$ Thus \begin{eqnarray*} S((P_2\Box G )^o)^TS((P_2\Box G )^o)&=& \left(\begin{array}{cc} -S(\G) & -I_n\\ I_n & S(\G)\end{array}\right) \left(\begin{array}{cc} S(\G) & I_n\\ -I_n & -S(\G)\end{array}\right)\\ &=& \left(\begin{array}{cc} S(\G)^T S(G)+I_n & 0\\ 0 & S(\G)^TS(\G)+I_n \end{array}\right)\\ &=& \left(\begin{array}{cc} (k+1)I_n & 0\\ 0 & (k+1)I_n \end{array}\right)=(k+1)I_n. \end{eqnarray*} \ezm \begin{figure}[hp] \unitlength=1.6mm \begin{picture}(120,34) \thinlines \drawthickdot{6.0}{28.0} \drawthickdot{16.0}{28.0} \drawthickdot{16.0}{18.0} \drawthickdot{6.0}{18.0} \drawthickdot{32.0}{28.0} \drawthickdot{42.0}{28.0} \drawthickdot{32.0}{18.0} \drawthickdot{42.0}{18.0} \drawpath{6.0}{28.0}{16.0}{28.0} \drawpath{16.0}{28.0}{16.0}{18.0} \drawcenteredtext{16.0}{6.0}{(a): $K_4$} \drawpath{16.0}{18.0}{6.0}{18.0} \drawpath{6.0}{18.0}{6.0}{28.0} \drawpath{6.0}{28.0}{16.0}{18.0} \drawpath{16.0}{28.0}{6.0}{18.0} \drawpath{32.0}{28.0}{42.0}{28.0} \drawpath{42.0}{28.0}{42.0}{18.0} \drawpath{42.0}{18.0}{32.0}{18.0} \drawpath{32.0}{18.0}{32.0}{28.0} \drawpath{32.0}{28.0}{42.0}{18.0} \drawpath{42.0}{28.0}{32.0}{18.0} \drawvector{32.0}{28.0}{8.0}{1}{0} \drawvector{32.0}{18.0}{8.0}{1}{0} \drawvector{32.0}{28.0}{0.0}{0}{1} \drawvector{32.0}{28.0}{8.0}{0}{-1} \drawvector{42.0}{18.0}{8.0}{0}{1} \drawvector{32.0}{28.0}{8.0}{1}{-1} \drawoval{79.0}{22.0}{6.0}{12.0}{} \drawcenteredtext{40.0}{6.0}{(b): An orientation of $K_4$} \drawcenteredtext{80.0}{20.0}{$\Gr_{r-1}$} \drawoval{95.0}{22.0}{6.0}{12.0}{} \drawcenteredtext{96.0}{20.0}{$\Gl_{r-1}$} \drawvector{82.0}{26.0}{10.0}{1}{0} \drawvector{82.0}{22.0}{10.0}{1}{0} \drawvector{82.0}{18.0}{10.0}{1}{0} \drawcenteredtext{86.0}{8.0}{(c): An orientation of $G_r.$ } \drawpath{42.0}{28.0}{34.0}{20.0} \drawvector{42.0}{28.0}{8.0}{-1}{-1} \end{picture} %\input{K_4.tex} \vspace*{-12mm} \caption{ The orientations of a family of $k$-regular graphs with the maximum skew energy}\label{maximum1} \end{figure} \begin{exa}\label{2reg} Let $H_1= P_2, H_2= P_2 \Box H_1 , \cdots, H_{d+1}=P_2 \Box H_d .$ Then $H_d$ is hypercube of dimension $d$. Since $P_2$ has an orientation with skew energy 2, using above theorem, we can obtain an orientation of the hypercube $H_d$ with the maximum skew energy $2^d \sqrt{d}$ for $d\geq 2.$ See also the Algorithm 1 in \cite{tian11}. \end{exa} \begin{exa}\label{3reg} Let $G_1=K_4, G_2= P_2 \Box K_4,\cdots, G_r=P_2 \Box G_{r-1}.$ In \cite{abw10}, an orientation of $K_4$ with skew energy $4\sqrt{3}$ is given, see (b) of Fig. \ref{maximum1}. Thus, we can obtain an oriented graph $\Gr_r$ of $G_r$ with the maximum skew energy $2^{r+1} \sqrt{r+2}.$ This also provides a family of $k$-regular graphs of order $n=2^{k-1}$ having an orientation with skew energy $n\sqrt{k}$ for $k \geq 3.$ \end{exa} \begin{center} \begin{figure}[h] \unitlength=1.2mm \begin{picture}(62,38) \thinlines \drawthickdot{12.0}{32.0} \drawthickdot{6.0}{26.0} \drawthickdot{18.0}{26.0} \drawthickdot{6.0}{18.0} \drawthickdot{18.0}{18.0} \drawthickdot{12.0}{12.0} \drawpath{12.0}{32.0}{18.0}{26.0} \drawpath{18.0}{26.0}{18.0}{18.0} \drawpath{18.0}{18.0}{12.0}{12.0} \drawpath{12.0}{12.0}{6.0}{18.0} \drawpath{6.0}{18.0}{6.0}{26.0} \drawpath{6.0}{26.0}{12.0}{32.0} \drawpath{12.0}{32.0}{12.0}{12.0} \drawpath{6.0}{26.0}{18.0}{18.0} \drawpath{18.0}{26.0}{6.0}{18.0} \drawthickdot{50.0}{32.0} \drawthickdot{44.0}{26.0} \drawthickdot{56.0}{26.0} \drawthickdot{44.0}{18.0} \drawthickdot{56.0}{18.0} \drawthickdot{50.0}{12.0} \drawpath{44.0}{26.0}{50.0}{32.0} \drawpath{50.0}{32.0}{56.0}{26.0} \drawpath{56.0}{26.0}{56.0}{18.0} \drawpath{56.0}{18.0}{50.0}{12.0} \drawpath{44.0}{26.0}{44.0}{26.0} \drawpath{44.0}{26.0}{44.0}{18.0} \drawpath{44.0}{26.0}{56.0}{26.0} \drawpath{44.0}{18.0}{50.0}{12.0} \drawpath{50.0}{32.0}{50.0}{12.0} \drawvector{50.0}{32.0}{4.0}{-1}{-1} \drawvector{50.0}{32.0}{4.0}{1}{-1} \drawvector{44.0}{26.0}{10.0}{1}{0} \drawpath{44.0}{18.0}{56.0}{18.0} \drawvector{44.0}{26.0}{4.0}{0}{-1} \drawvector{56.0}{26.0}{6.0}{0}{-1} \drawvector{50.0}{32.0}{12.0}{0}{-1} \drawvector{56.0}{18.0}{10.0}{-1}{0} \drawvector{50.0}{12.0}{0.0}{0}{1} \drawvector{56.0}{18.0}{4.0}{-1}{-1} \drawcenteredtext{50.0}{6.0}{$\overrightarrow{G_2}$} \drawvector{44.0}{18.0}{4.0}{1}{-1} \drawcenteredtext{12.0}{6.0}{$\overrightarrow{G_1}$} \drawvector{12.0}{12.0}{0.0}{0}{1} \drawvector{12.0}{12.0}{0.0}{0}{1} \drawvector{12.0}{12.0}{4.0}{1}{1} \drawvector{12.0}{12.0}{14.0}{0}{1} \drawvector{12.0}{12.0}{4.0}{-1}{1} \drawvector{6.0}{26.0}{6.0}{0}{-1} \drawvector{18.0}{26.0}{4.0}{0}{-1} \drawvector{6.0}{26.0}{4.0}{1}{1} \drawvector{12.0}{32.0}{4.0}{1}{-1} \drawvector{18.0}{26.0}{12.0}{-3}{-2} \drawvector{18.0}{18.0}{12.0}{-3}{2} \end{picture} %\input{isks} \caption{ Orientations of two non-isomorphic 3-regular graphs on 6 vertices having the same skew spectra.}\label{isn} \end{figure} \end{center} There are two non-isomorphism 3-regular graphs $G_1$ and $G_2$ on 6 vertices, the orientations on them depicted in Fig. \ref{isn} have the same skew spectrum $\pm 2\I, \pm 2\I,\pm \I$. Moreover they have the maximum skew energy among all orientations of $G_1$ and $G_2,$ respectively, but their skew energies are less than $6\sqrt{3}.$ So there is no 3-regular graph on 6 vertices having an orientation with skew energy $6\sqrt{3}.$ Recall that the characteristic polynomial of $S(\G)$ is as in (2.4). In \cite{hsz}, the following integral formula for the skew energy of $\G$ was given: $${\cal E}(\G)= \frac{1}{\pi} \int^{\infty}_{-\infty}\frac{1}{t^2}\log(1+\sum_{k=1}^{\lfloor \frac{n}{2}\rfloor} c_{2k}t^{2k})dt. \eqno{(3.1)}$$ It follows from above integral formula that ${\cal E}({\G})$ is an increasing function of $c_{2k}(\G)$, $k = 0$, $1$, $\cdots$, $\lfloor\frac{n}{2}\rfloor$. Consequently, if ${G^{\sigma}_1}$ and ${G^{\tau}_2}$ are oriented graphs of $G_1$ and $G_2,$ respectively, for which $$ c_{2i}(G^{\sigma}_1)\geq c_{2i}(G^{\tau}_2) \mbox{ for all } \lfloor{\frac{n}{2}}\rfloor\geq i\geq 0 \eqno{(3.2)} $$ $$\mbox{ then } {\cal E}(G^{\sigma}_1)\geq {\cal E}(G^{\tau}_2). \eqno{(3.3)} $$ Equality in Eq. (3.3) is attained only if Eq. (3.2) is an equality for all $\lfloor{\frac{n}{2}}\rfloor\geq i\geq 0$. \begin{lem} If $G$ has an orientation $\sigma$ such that every even cycle is oddly oriented, then $\G$ has the maximal skew energy among all orientations of $G.$ \end{lem} \zm Let $^{o}$ be the orientation of $G$ such that all even cycles are oddly oriented and let $\sigma$ be any orientation of $G.$ By Eq. (2.5), we have \begin{eqnarray*} c_{2i}(\G)&=& \sum_{L' \in {\cal EL}(\G)_{2i}}(-2)^{p_e(L')}2^{p_o(L')} \leq \sum_{L' \in {\cal EL}(\G)_{2i}}2^{p_e(L')+p_o(L')} \\ &\leq &\sum_{L \in {\cal EL}(G^o)_{2i}}(-2)^{p_e(L)}2^{p_o(L)}=c_{2i}(G^o). \end{eqnarray*} Thus ${\cal E}(\G)\leq {\cal E}(G^o).$ \ezm If in $\G$ , every even cycle is evenly oriented, we do not know if $\G$ has the minimal skew energy among all orientations of $G.$ Which graphs have an orientation $\sigma$ such that all even cycles are oddly oriented? Fisher and Little gave a characterization for such graphs as follows: \begin{thm}(\cite{fl03} A graph has an orientation under which every cycle of even length is oddly oriented if and only if the graph contains no subgraph which is, after the contraction of at most one cycle of odd length, an even subdivision of $K_{2,3}.$ \end{thm} For bipartite graphs, in \cite{zhangli10}, Zhang and Li show that there exists an orientation of a bipartite graph $G$ such that all even cycles are oddly oriented if and only if $G$ contains no even subdivision of $K_{2,3}.$ Moreover, If a bipartite graph contains no even subdivision of $K_{2,3}$ then it must be planar. The following lemma provides a family of graphs having an orientation under which every cycle of even length is oddly oriented. \begin{lem}\cite{zhangyan06} Let $T$ be a tree and $\sigma$ be an arbitrary orientation of $T.$ Then the oriented graph $(P_2 \Box T)^o$ has every even cycle oddly oriented. \end{lem} \begin{cor} Let $T$ be a tree. Then the oriented graph $(P_2 \Box T )^o$ has the maximal skew energy among all orientations of $P_2 \Box T.$ \end{cor} Let $\sigma$ is an orientation of $G$ such that $\G$ has the minimum (maximum, respectively) skew energy among all orientations of $G.$ It is a natural question that which orientations of $P_2\Box G$ yield the minimum (maximum, respectively) skew energy? One may think the oriented graph $P_2 \Box \G$ ( $(P_2 \Box \G)^o,$ respectively) would be a candidate. The following example shows that this is not true for the minimum skew energy. We conjecture $(P_2 \Box \G)^o$ has the maximum skew energy among all orientations of $P_2 \Box G$ if $\G$ has the maximum skew energy among all orientations of $G.$ \begin{figure}[htbp] \unitlength=1.2mm \begin{picture}(100,42) \thinlines \drawthickdot{16.0}{34.0} \drawthickdot{36.0}{34.0} \drawthickdot{16.0}{16.0} \drawthickdot{36.0}{16.0} \drawvector{16.0}{34.0}{12.0}{1}{0} \drawthickdot{58.0}{34.0} \drawvector{36.0}{34.0}{10.0}{0}{-1} \drawvector{36.0}{16.0}{12.0}{-1}{0} \drawthickdot{22.0}{28.0} \drawthickdot{30.0}{28.0} \drawthickdot{22.0}{22.0} \drawthickdot{30.0}{22.0} \drawpath{16.0}{34.0}{36.0}{34.0} \drawpath{36.0}{34.0}{36.0}{16.0} \drawpath{36.0}{16.0}{16.0}{16.0} \drawpath{16.0}{16.0}{16.0}{34.0} \drawpath{16.0}{34.0}{22.0}{28.0} \drawpath{22.0}{28.0}{30.0}{28.0} \drawpath{30.0}{28.0}{30.0}{22.0} \drawpath{30.0}{22.0}{22.0}{22.0} \drawpath{22.0}{22.0}{22.0}{28.0} \drawpath{22.0}{22.0}{16.0}{16.0} \drawpath{30.0}{28.0}{36.0}{34.0} \drawpath{30.0}{22.0}{36.0}{16.0} \drawcenteredtext{16.0}{36.0}{1} \drawvector{22.0}{28.0}{4.0}{1}{0} \drawvector{30.0}{28.0}{4.0}{0}{-1} \drawvector{30.0}{22.0}{4.0}{-1}{0} \drawvector{22.0}{22.0}{4.0}{0}{1} \drawvector{22.0}{28.0}{4.0}{-1}{1} \drawvector{30.0}{28.0}{4.0}{1}{1} \drawvector{30.0}{22.0}{4.0}{1}{-1} \drawvector{22.0}{22.0}{4.0}{-1}{-1} \drawvector{16.0}{16.0}{14.0}{0}{1} \drawthickdot{78.0}{34.0} \drawthickdot{58.0}{16.0} \drawthickdot{78.0}{16.0} \drawthickdot{64.0}{28.0} \drawthickdot{72.0}{28.0} \drawthickdot{64.0}{22.0} \drawthickdot{72.0}{22.0} \drawpath{58.0}{34.0}{78.0}{34.0} \drawpath{78.0}{34.0}{78.0}{16.0} \drawpath{78.0}{16.0}{58.0}{16.0} \drawpath{58.0}{16.0}{58.0}{34.0} \drawpath{58.0}{34.0}{64.0}{28.0} \drawpath{64.0}{28.0}{72.0}{28.0} \drawpath{72.0}{28.0}{72.0}{22.0} \drawpath{72.0}{22.0}{64.0}{22.0} \drawpath{64.0}{22.0}{64.0}{28.0} \drawpath{64.0}{22.0}{58.0}{16.0} \drawpath{72.0}{22.0}{78.0}{16.0} \drawpath{72.0}{28.0}{78.0}{34.0} \drawvector{58.0}{34.0}{10.0}{1}{0} \drawvector{78.0}{34.0}{10.0}{0}{-1} \drawvector{78.0}{16.0}{12.0}{-1}{0} \drawvector{58.0}{16.0}{10.0}{0}{1} \drawvector{64.0}{28.0}{4.0}{1}{0} \drawvector{72.0}{28.0}{4.0}{0}{-1} \drawvector{72.0}{22.0}{6.0}{-1}{0} \drawvector{64.0}{28.0}{4.0}{0}{-1} \drawvector{64.0}{28.0}{4.0}{-1}{1} \drawvector{72.0}{28.0}{4.0}{1}{1} \drawvector{72.0}{22.0}{4.0}{1}{-1} \drawvector{64.0}{22.0}{4.0}{-1}{-1} \drawcenteredtext{38.0}{34.0}{2} \drawcenteredtext{38.0}{14.0}{3} \drawcenteredtext{16.0}{14.0}{4} \drawcenteredtext{22.0}{30.0}{5} \drawcenteredtext{30.0}{30.0}{6} \drawcenteredtext{30.0}{20.0}{7} \drawcenteredtext{22.0}{20.0}{8} \drawcenteredtext{56.0}{36.0}{1} \drawcenteredtext{78.0}{36.0}{2} \drawcenteredtext{78.0}{14.0}{3} \drawcenteredtext{58.0}{14.0}{4} \drawcenteredtext{64.0}{30.0}{5} \drawcenteredtext{72.0}{30.0}{6} \drawcenteredtext{72.0}{20.0}{7} \drawcenteredtext{64.0}{20.0}{8} \end{picture} %\input{cube2.tex} \caption{Two orientations of $P_2 \Box C_4$.}\label{cube2} \end{figure} \begin{exa} Let $G=P_2 \Box C_4$ ($G$ is the hypercube $Q_3$, in fact) and $C_4^e$ be an oriented graph of $C_4$ such that $C_4$ is evenly oriented. Then $Sp(C_4^e)=\{2\I,-2\I,0,0\}, {\cal E}(C_4^e)=4$ has the minimum skew energy among all orientations of $C_4.$ The left orientation in Figure \ref{cube2}, which is $P_2\Box C_4^e$ has skew energy 12 but the right orientation has skew energy (about 11.5) less than 12. \end{exa} \vspace*{6mm} {\em Acknowledgment:} The authors would like to express their sincere gratitude to the referee for a very careful reading of the paper and for all his or her insightful comments and valuable suggestions, which made a number of improvements in this paper. This project was supported by National Natural Science Foundation of China (No.11171102) and the Program for Science and Technology Innovative Team in Higher Educational Institution of Hunan Province. \begin{thebibliography}{99} \bibitem{abw10}{C. Adiga, R. Balakrishnan and Wasin So, } {The skew energy of a digraph,} {\it Linear Algebra and Its Applications} 432 (2010) 1825--1835. \bibitem{cds80}{ D. M. Cvetkovic M. Doob and H. Sachs, }{\it Spectra of Graphs, Theory and Application, 3rd edition} { Academic Press, New York, 1995.} \bibitem{fl03}{I. Fischer, C. H. C. Little, }{Even circuits of prescribed clockwise parity,} {\it The Electronic Journal of Combinatorics} 10(2003), \#R45. \bibitem{ht11}{Y. Hou and T. Lei, } {Characteristic polynomials of skew-adjacency matrices of oriented graphs,}{\it The Electronic Journal of Combinatorics} 18(2011), \#P156. \bibitem{hsz} {Y. Hou, X. Shen, C. Zhang, }{ Oriented unicyclic graph with extremal skew energy,} arXiv:1108.6229. \bibitem{lp88}{L. Lov\'asz and M. Plummer, } {\it Matching Theory,} { Ann. of Discrete Math. 29, North-Holland, New York,1988.} \bibitem{ss09}{B. Shader and Wasin So, }{Skew spectra of oriented graphs,} {\it The Electronic Journal of Combinatorics} 16 (2009), \#N32. \bibitem{tian11}{ Gui-Xian Tian,} { On the skew energy of orientations of hypercubes,} {\it Linear Algebra and Its Applications} 435 (2011)2140--2149. \bibitem{yanzhang03}{Weigen Yan and Fuji Zhang, }{Enumeration of perfect matchings of a type of Cartesian products of graphs, }{\it Discrete Appl. Math. 154(2006) 145--157.} \bibitem{zhangyan06}{Fuji Zhang and Weigen Yan,}{Enumeration of perfect matchings in type of graphs with reflective symmetry, }{\it MATCH Commun. Math. Comput. Chem 48 48(2003):117--124.} \bibitem{zhangli10}{Heping Zhang and Wei Li, }{Computing the permanental polynomials of bipartite graphs by Pfaffian orientaion, arXiv:1010.1113v1.} \end{thebibliography} \end{document} If one of $G$ and $H$ is a path, we will define another orientation of $G\Box H$ and determine its skew spectrum. As all orientations of a acyclic graph are switching equivalent, without losing generality, we assume that $H=P_m,$ the path with $m$ vertices $1,2,\cdots,m$ and the orientations of the edges are from $i$ to $i+1$ for $i=1,2,...,m-1.$ They also pointed out that it is not known which $k$-regular graphs admit an orientation with $S(G)^TS(\G)=kI.$