\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.$
