% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P18}{20(4)}{2013}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}
\usepackage{mathrsfs,subfigure,enumerate}
% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{algorithm}[theorem]{Algorithm}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Skew spectra of oriented bipartite graphs}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{A. Anuradha\qquad R. Balakrishnan\\
\small Department of Mathematics\\[-0.8ex]
\small Bharathidasan University\\[-0.8ex]
\small Tiruchirappalli 620024, India\\
\small\tt radha.anu.am@gmail.com \qquad mathbala@sify.com\\
\and
Xiaolin Chen \qquad Xueliang Li \qquad Huishu Lian \\
\small Center for Combinatorics and LPMC-TJKLC\\[-0.8ex]
\small Nankai University\\[-0.8ex]
\small Tianjin 300071, P. R. China\\
\small\tt chxlnk@163.com \qquad lxl@nankai.edu.cn \qquad lhs6803@126.com\\
\and
Wasin So\\
\small Department of Mathematics\\[-0.8ex]
\small San Jose State University\\[-0.8ex]
\small San Jose, California 95192--0103, U.S.A.\\
\small\tt wasin.so@sjsu.edu
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{April 30, 2013}{Oct 28, 2013}{Nov 15, 2013}\\
\small Mathematics Subject Classifications: 05C20, 05C50, 05C75}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\vspace*{-2ex}
\begin{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, {\it The 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 are optional
  \medskip\noindent \textbf{Keywords:} oriented bipartite graphs; skew energy; skew spectrum; canonical orientation; parity-linked orientation; switching-equivalence
\end{abstract}

\section{Introduction}

Let $G=(V,E)$ be a finite simple undirected graph of order $n$ with $V=\{ v_1, v_2, \ldots, v_n \}$ as its vertex set and $E$ as its edge set. An orientation $\phi$ of $E$ results in the oriented graph $G^{\phi}=(V,\Gamma),$ where $\Gamma$ is the arc set of $G^{\phi}.$ The adjacency matrix of $G$ is the  $n\times n$ matrix $A=(a_{ij}),$ where $a_{ij}=1$ if $(v_i,v_j)\in E$ and $a_{ij}=0$ otherwise. As the matrix $A$ is real and symmetric, all its eigenvalues are real. The spectrum of $G,$ denoted by $Sp(G),$ is the spectrum of $A.$ The energy $\mathcal{E}(G)$ of a graph $G$ of order $n,$ introduced by Ivan Gutman \cite{Gut78} in 1978, is defined as the sum of the absolute values of its eigenvalues. The skew adjacency matrix of the oriented graph $G^\phi$ is the $n \times n$ matrix $S(G^\phi) = (s_{ij}),$ where $s_{ij} = 1 = -s_{ji}$ whenever $(v_i,v_j) \in \Gamma(G^{\phi})$ and $s_{ij}=0$ otherwise. As the matrix $S(G^\phi)$ is real and skew symmetric, its eigenvalues are all pure imaginary. The skew spectrum of $G^{\phi}$ is the spectrum of $S(G^{\phi}).$ The concept of graph energy was recently generalized to oriented graphs as skew energy by Adiga, Balakrishnan and Wasin So in \cite{ABS}. The skew energy $\mathcal{E}_S(G^{\phi})$ of an oriented graph $G^{\phi}$ is defined as the sum of the absolute values of all the eigenvalues of $S(G^{\phi}).$ For the properties of the energy and spectrum of a graph, the reader may refer to \cite{RB2,GLZ,LSG}, and for skew energy and skew spectrum of an oriented graph, to \cite{ABS,SK,HL,LL,SS}. We follow \cite{RB2} for standard graph theoretic notation.

By a cycle in $G^{\phi},$ we refer to not necessarily a directed cycle. An oriented even cycle is classified into two types based on its structure. An even cycle $C$ of $G^{\phi}$ is said to be evenly or oddly oriented according as the number of arcs of $C$ in each direction is even or odd \cite{HL}.

Let $\mathscr{G}$ denote the family of graphs without even cycles. In \cite{SK}, Cavers et al. have proved the following result.

\begin{theorem}[Cavers et al. \cite{SK}]\label{5tsk1}
The skew spectrum of $G^{\phi}$ remains invariant under any orientation $\phi$ of $G$ if and only if $G$ contains no even cycles, that is, $G\in \mathscr{G}.$
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Oriented bipartite graphs $G^{\phi}$ with $Sp_S(G^{\phi}) = {\bf{i}} Sp(G)$}
Let $G=G(X,Y)$ be a bipartite graph with bipartition $(X,Y).$ The {\it canonical orientation} of $G$ is that orientation which orients all the edges from one partite set to the other. It is immaterial if it is from $X$ to $Y$ or from $Y$ to $X.$ Shader and So \cite{SS} have shown that for the canonical orientation $\sigma$ of $G(X,Y),$
\begin{equation}\label{neq51}
Sp_S(G^{\sigma}) = {\bf{i}} Sp(G).
\end{equation}

From this point onward, $\sigma$ stands for the canonical orientation with respect to a bipartite graph $G$ with a fixed bipartition $(X,Y).$

Let $G^{\phi}$ be an oriented graph of order $n.$ An even cycle $C_{2k}$ of length $2k$ in $G^{\phi}$ is said have a {\it parity-linked orientation} if it is evenly oriented whenever $k$ is even and oddly oriented whenever $k$ is odd. If every even cycle in $G^{\phi}$ has a parity-linked orientation, then the orientation $\phi$ is defined to be a parity-linked orientation of $G.$ (The parity-linked orientation is termed as uniform orientation in \cite{CH}.)

In \cite{CH}, Cui and Hou have given a characterization of oriented graphs $G^{\phi}$ that satisfy Equation (\ref{neq51}) by using the parity-linked orientation of graphs.

\begin{theorem}[\cite{CH}]\label{5t6}
Suppose $G^{\phi}$ is an oriented bipartite graph with $G$ as its underlying graph. Then $Sp_S(G^{\phi}) = {\bf{i}} Sp(G)$ if and only if the orientation $\phi$ of $G$ is parity-linked.
\end{theorem}

Let $U$ be any proper subset of $V(G)$ of an oriented graph $G^{\phi_1}$ and let $\overline{U}=V(G)\setminus U$ be its complement. Reversing the orientations of all the arcs between $U$ and $\overline{U}$ results in another oriented graph $G^{\phi_2}.$ This process is called the {\it switch} of $G^{\phi_1}$ with respect to $U.$ The oriented graph got by two successive switches with respect to $U_1$ and $U_2$ is just the oriented graph obtained from $G$ by the switch with respect to the set $U_1\Delta U_2,$ the symmetric difference of $U_1$ and $U_2.$

Suppose $\phi_1$ and $\phi_2$ are two orientations of a graph $G.$ Then $G^{\phi_1}$ and $G^{\phi_2}$ are said to be {\it switching-equivalent} if $G^{\phi_2}$ can be obtained from $G^{\phi_1}$ by a switch. It is clear that switching-equivalence among the set $\mathscr{O}$ of all orientations of a graph $G$ is indeed an equivalence relation on $\mathscr{O}.$ The following result is proved in \cite{ABS}.

\begin{theorem}[\cite{ABS}]\label{5t3}
Let $\phi_1$ and $\phi_2$ be two orientations of a graph $G.$ If $G^{\phi_1}$ and $G^{\phi_2}$ are switching-equivalent, then $Sp_S(G^{\phi_1})=Sp_S(G^{\phi_2}).$
\end{theorem}

We mention that the converse of Theorem \ref{5t3} is not true for non-bipartite graphs.

\begin{example}\label{5ex5}
Consider the two orientations $\phi_1$ and $\phi_2$ of the cycle graph $C_5$ as given in Figure \ref{5fn3}.

\begin{figure}[!h]
\centering
\includegraphics[width=2.75 in]{contra1.eps}
\caption{Two orientations of the cycle graph $C_5$ }
\label{5fn3}
\end{figure}

Since $C_5\in \mathscr{G},$ the family of graphs without even cycles, by Theorem \ref{5tsk1},
\[
Sp_S(C_{5}^{\phi_1}) = Sp_S(C_{5}^{\phi_2}).
\]
The oriented cycle $C_{5}^{\phi_1}$ has $5$ arcs in one direction (clockwise) while $C_{5}^{\phi_2}$ has $4$ arcs in the same direction for the given labeling. Any switch in $C_{5}^{\phi_1}$ will cause an even number of changes in the number of arcs in both the directions. Hence the $5$ arcs in the clockwise direction can only become either $3$ arcs or $1$ arc in the clockwise direction after any switch but never $4$ arcs in the clockwise direction. Therefore $\phi_1$ and $\phi_2$ are not switching-equivalent in $C_5.$
\end{example}

In \cite{CH}, Cui and Hou conjectured that for an oriented bipartite graph $G^{\phi},$ $Sp_S(G^{\phi}) = {\bf{i}}Sp(G)$ if and only if $G^{\phi}$ is switching-equivalent to $G^{\sigma},$ where $\sigma$ is the canonical orientation of $G.$ In this paper, we settle the above conjecture in the affirmative and present it as the following theorem.

\begin{theorem}[Conjectured in \cite{CH}]\label{5t5}
Suppose $\phi$ is an orientation of a bipartite graph $G=G(X,Y).$ Then $Sp_S(G^{\phi}) = {\bf{i}}Sp(G)$ if and only if $G^{\phi}$ is switching-equivalent to $G^{\sigma},$ where $\sigma$ is the canonical orientation of $G.$
\end{theorem}
\begin{proof} Without loss of generality, we may assume that $G$ is a connected graph.

\noindent {\it Sufficiency.} If $G^{\phi}$ and $G^{\sigma}$ are switching-equivalent, then by Theorem \ref{5t3}, $Sp_S(G^{\phi}) = Sp_S(G^{\sigma}) = {\bf{i}} Sp(G)$ (where the second equality follows from (\ref{neq51})).

\noindent {\it Necessity.} We prove by induction on the number of edges $m$ of the bipartite graph $G.$ The result is trivial for $m=1.$

Assume that the result is true for all bipartite graphs with at most $m-1 (m\geq 2)$ arcs. Let $G$ be a bipartite graph with $m$ edges and $(X,Y)$ be the bipartition of the vertex set of $G.$ Suppose that $\phi$ is an orientation of $G$ such that $Sp_S(G^{\phi}) = {\bf{i}} Sp(G).$ We have to prove that $\phi$ is switching-equivalent to $\sigma.$ Let $e$ be any edge of $G.$ By Theorem \ref{5t6}, $\phi$ is a parity-linked orientation of $G^{\phi}$ and hence of $(G-e)^{\phi}.$ Consequently, $(G-e)^{\phi_e}$ has a parity-linked orientation, where $\phi_e$ is the restriction of $\phi$ to the graph $G-e.$ So again by Theorem \ref{5t6},
\[
Sp_S((G-e)^{\phi_e}) = {\bf{i}} Sp(G-e).
\]

Consequently, by induction hypothesis, $(G-e)^{\phi_e}$ is switching-equivalent to $(G-e)^{\sigma_e},$ where $\sigma_e$ is the restriction of $\sigma$ to the graph $G-e.$

Let $\alpha$ be the switch that takes $(G-e)^{\phi_e}$ to $(G-e)^{\sigma_e}$ effected by the subset $U$ of $V(G-e)=V(G).$ We claim that $\alpha$ takes $\phi$ to $\sigma$ in $G.$ If not, then the resulting oriented graph $G^{\phi'}$ will be of the following type: All the arcs of $G-e$ will be oriented from one partite set (say, $X$) to the other (namely, $Y$) while the arc $e$ will be oriented in the reverse direction, that is, from $Y$ to $X$ (See Figure \ref{nf3}).

\begin{figure}[!h]
\centering
\includegraphics[width=3 cm]{nf4.eps}
\caption{The oriented bipartite graph $G^{\phi'}$ in Theorem \ref{5t5}}
\label{nf3}
\end{figure}

Consider first the case when $e$ is a cut edge of $G.$ The subgraph $G-e$ will then consist of two components with vertex sets, say, $S_1$ and $S_2.$ Now switch with respect to $S_1.$ This will change the orientation of the only arc $e$ and the resulting orientation is $\sigma.$ Consequently, $\phi$ is switching-equivalent to $\sigma.$

Note that the above argument also takes care of the case when $G$ is a tree since each edge of $G$ will then be a cut edge. Hence we now assume that $G$ contains an even cycle $C_{2k}$ containing the arc $e$ and complete the proof. But then any such $C_{2k}$ has $k-1$ arcs in one direction and $k+1$ arcs in the opposite direction (see Figure \ref{5f2}) thereby not admitting a parity-linked orientation. Hence this case can not arise. Consequently, $\phi$ is switching-equivalent to $\sigma$ in $G.$
\end{proof}

\begin{figure}[!h]
\centering
\subfigure [An evenly oriented $C_6$ in $G^{\phi'}$]
{ \includegraphics[width=1 in]{fig2b.eps}}\hspace{3cm}
\subfigure [An oddly oriented $C_8$ in $G^{\phi'}$]
{ \includegraphics[width=1.2 in, height = 4.5cm]{fig2a.eps}}
\caption{Cycle $C_{2k}$ for $k = 3,4$ in $G^{\phi'}$}
\label{5f2}
\end{figure}

Theorem \ref{5t6} provides a nice characterization for an oriented bipartite graph $G^{\phi}$ to have the property that $Sp_S(G^{\phi}) = {\bf{i}} Sp(G).$ But it requires to check if every cycle in $G^{\phi}$ possesses a parity-linked orientation. A natural question is the following: Is it possible to reduce the number of checks to determine whether an oriented graph $G^{\phi}$ has a parity-linked orientation? Our next result provides an answer in this direction.

%As a consequence, we obtain a polynomial time algorithm to check if a given oriented bipartite graph has the property that $Sp_S(G^{\phi}) = {\bf{i}} Sp(G).$

\begin{theorem}\label{5t7}
Let $G$ be a bipartite graph and $\phi$ be an orientation of $G.$ If $\phi$ induces a parity-linked orientation on every chordless (even) cycle of $G,$ then $Sp_S(G^{\phi}) = {\bf{i}} Sp(G).$
\end{theorem}
\begin{proof}
By virtue of Theorem \ref{5t6}, it suffices to show that if $\phi$ induces a parity-linked orientation on every chordless (even) cycle of $G,$ then $\phi$ induces a parity-linked orientation on every cycle of $G.$ If the result were not true, then there exists a cycle $C_{2\ell}$ in $G^{\phi}$ of least length $2\ell$ such that $\phi$ does not induce a parity-linked orientation on $C_{2\ell}.$ This of course means that $C_{2\ell}$ is evenly (resp. oddly) oriented if $l$ is odd (resp. even). By hypothesis, $C_{2\ell}$ contains a chord $x_1 y_1.$ Suppose that $C_{2\ell} = x_1 x_2 \ldots x_{\ell_1} y_1 y_2 \ldots y_{2\ell-\ell_1} x_1$ in clockwise direction. Consider the two cycles $C_1 = x_1 x_2 \ldots x_{\ell_1} y_1 x_1$  and $C_2 = x_1 y_1 y_2 \ldots y_{2\ell-\ell_1} x_1$ with respective lengths $\ell_1 + 1$ and $2\ell-\ell_1+1$ in clockwise direction. Note that $C_1$ and $C_2$ are also even ($G$ being bipartite). Suppose that $C_1$ and $C_2$ contain respectively $r_1$ and $r_2$ arcs in the clockwise direction. By the choice of $C_{2\ell},$ $C_1$ and $C_2$ possess the parity-linked orientation. Hence
\[
\dfrac{\ell_1+1}{2} \equiv r_1({\textnormal{mod }} 2) {\textnormal{ and }} \dfrac{2\ell-\ell_1+1}{2} \equiv r_2({\textnormal{mod }} 2).
\]
It follows that $\ell+1 \equiv (r_1 + r_2)({\textnormal{mod }} 2).$ Observe that if the arc corresponding to $x_1 y_1$ is clockwise in $C_1,$ then it must be anticlockwise in $C_2$ and vice versa. This of course means that $C_{2\ell}$ also admits the parity-linked orientation. This contradiction proves the result.
\end{proof}

Combining Theorem \ref{5t6} and Theorem \ref{5t7}, we obtain immediately the following corollary.

\begin{corollary}\label{5c1}
Let $G$ be a bipartite graph and $\phi,$ an orientation of $G.$ Then $Sp_S(G^{\phi}) = {\bf{i}} Sp(G)$ if and only if $\phi$ induces a parity-linked orientation on all the chordless cycles of $G.$
\end{corollary}

\begin{remark}
Let $\mathscr{C}$ denote the set of all cycles of a bipartite graph $G.$ A subset $\mathscr{S}$ of $\mathscr{C}$ is called a {\it generating set} of $\mathscr{C}$ if for any cycle $C$ of $\mathscr{C}$ either $C\in \mathscr{S}$ or there is a sequence of cycles $C_1, C_2, \ldots, C_k$ in $\mathscr{S}$ such that $C = ((C_1 \Delta C_2) \Delta C_3) \ldots C_k$ and for $2\leq p\leq k-1,$ $((C_1 \Delta C_2) \Delta C_3) \ldots \Delta C_{p}$ are all cycles of $G.$ With this notation, one can prove that for any oriented bipartite graph $G^{\phi},$ $Sp_S(G^{\phi}) = {\bf{i}} Sp(G)$ if and only if $\phi$ induces a parity-linked orientation for every cycle in a generating set $\mathscr{S}$ of $\mathscr{C}$ in $G.$ Actually, the set of all chordless cycles of a graph $G$ is a generating set of the set of all cycles of $G.$
\end{remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Switching-equivalence in oriented hypercubes}

We present below an illustration for Theorem \ref{5t5}. In \cite{AB1}, Anuradha and Balakrishnan have constructed an oriented hypercube $Q_{d}^{\phi}$ for which $Sp_S(Q_d^{\phi}) = {\bf{i}} Sp(Q_d), \,\ d\geq 1.$

By Theorem \ref{5t5}, $\phi$ must be switching-equivalent to the canonical orientation $\sigma$ of $Q_d.$ We now determine a switching set $U_d$ in $Q_{d}^{\phi}$ that takes $\phi$ to $\sigma.$

We first recall the algorithm given in \cite{AB1} by means of which $Q_d^{\phi},$  $d\geq 1,$ is constructed.

\begin{algorithm}\label{algnw1}
\rm
The hypercube $Q_d,$ $d\geq 2,$  can be constructed by taking two copies of $Q_{d-1}$ and making the corresponding vertices in the two copies adjacent. Let $V(Q_d) = \{ (\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_d) ~:~ \varepsilon_i = 0 {\textnormal{ or }} 1\}$ be the vertex set of $Q_d.$
\begin{enumerate}[\noindent 1.]
\item For $Q_1= K_2,$ $V(Q_1) = \{ (0), (1) \}.$ Set $(1,0) \in \Gamma(Q_1^{\phi}).$
\item Assume that for $i=1, 2, \ldots, k (<d),$ the oriented hypercube $Q_k^{\phi}$ has been constructed. For $i=k+1,$ the oriented hypercube $Q_{k+1}^{\phi}$ is formed as follows:
    \begin{enumerate}[(a).]
    \item Take two copies $C_0^{(k)}$ and $C_1^{(k)}$ of $Q_{k}^{\phi}.$ Reverse the orientation of all the arcs in $C_1^{(k)}.$
    \item For $j=0,1,$ relabel the vertices of $C_j^{(k)}$ by adding $j$ as the first coordinate, that is, if $(\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_k)\in Q_k,$ then the vertex $(0, \varepsilon_1, \varepsilon_2, \ldots, \varepsilon_k) \in C_0^{(k)}$ and the vertex $(1, \varepsilon_1, \varepsilon_2, \ldots, \varepsilon_k) \in C_1^{(k)}.$
    \item Let $(X_0,Y_0)$ be the bipartition of $V(Q_k)$ in $C_0^{(k)}$ such that the vertex labeled $(0,0,\ldots, 0)$ is in $X_0.$ Set the corresponding bipartition in $C_1^{(k)}$ as $(X_1,Y_1).$ (Note that the vertex labeled $(1,0,0, \ldots, 0)\in X_1.$) Consequently $X = X_0 \cup Y_1$ and $Y = X_1 \cup Y_0$ form the bipartition of $V(Q_{k+1}).$
    \item Add an edge between the vertices of $C_0^{(k)}$ and $C_1^{(k)}$ that differ in exactly the first coordinate. For each such edge, assign the orientation from $X_0$ to $X_1$ and from $Y_1$ to $Y_0$ (see Figure \ref{nf1}). This yields the oriented hypercube $Q_{k+1}^{\phi}.$ (See Figure \ref{nf2}.)
    \end{enumerate}
\item If $k+1 = d,$ stop; else take $k\leftarrow k+1,$ return to Step $2.$ $\hfill\Box$
\end{enumerate}
\end{algorithm}

\begin{figure}[!h]
\centering
\includegraphics[width=3.25 in]{nf3.eps}
\caption{Example for Step 2(d) in Algorithm \ref{algnw1} }
\label{nf1}
\end{figure}
\begin{figure}[!h]
\centering
\includegraphics[width=5.5 cm]{nf2.eps}
\caption{Orientation $\phi$ of hypercube $Q_i,$ $i=1,2,3,$ defined in Algorithm \ref{algnw1} }
\label{nf2}
\end{figure}

Let $(X,Y)$ be the bipartition of $V(Q_{d}^{\phi})$ for $d\geq 1$ such that the vertex $(0,0,\ldots,0)$ is in $X.$ It is then easy to observe from the construction of $Q_{d}^{\phi}$ that the indegree, $\deg^{+}(u),$ of each vertex $u \in X$ is $1$ while the outdegree $\deg^{-}(v)$ of each vertex $v\in Y$ is $1$ in $Q_{d}^{\phi}.$

For each $d\geq 1,$ we now define a set $U_d \subset V(Q_{d}^{\phi})$ recursively as follows: For the oriented hypercube $Q_{1}^{\phi},$ set $U_1 = \{ (0) \}.$ For $k\geq 1~ (k<d),$ assume that the set $U_k$ has been determined. Form the set $U_{k+1}$ of the oriented hypercube $Q_{k+1}^{\phi}$ by taking, for each vertex $v = (\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_k) \in U_k$ of the hypercube $Q_{k}^{\phi},$ the vertices $v_0 = (0, \varepsilon_1, \varepsilon_2, \ldots, \varepsilon_k)$ and $v_1 = (1, \varepsilon_1, \varepsilon_2, \ldots, \varepsilon_k).$ Note that in the oriented hypercube $Q_{k+1}^{\phi},$ if $U_k^0$ and $U_k^1$ are the two sets corresponding to $U_k$ in the two copies $C_0^{(k)}$ and $C_1^{(k)}$ of $Q_{k}^{\phi}$ then $U_{k+1} = U_k^0 \cup U_k^1$ and $|U_{k+1}| = 2^k.$

We now show that for each $d\geq 1,$ a switch with respect to the set $U_d$ in the oriented hypercube $Q_{d}^{\phi}$ results in the canonical orientation $\sigma$ of $Q_d.$

\begin{theorem}
Suppose $Q_{d}^{\phi}$ is the oriented hypercube obtained by Algorithm \ref{algnw1}. Let $U_{d} \subset V(Q_{d}^{\phi})$ be determined as above. Then a switch with respect to the set $U_d,$ for $d = 1, 2, \ldots,$ yields the canonical orientation $\sigma$ of $Q_d.$
\end{theorem}
\begin{proof}
Proof by induction on $d.$ It is obvious for $d=1,2.$ (For $d=1,2,$ $U_1 = \{(0)\}$ and $U_2 = \{ (0,0), (1,0) \} .$)

Suppose that a switch with respect to the set $U_k\,\ (k<d),$ yields the canonical orientation in the oriented hypercube $Q_{k}^{\phi}.$ Consider the set $U_{k+1}$ of the oriented hypercube $Q_{k+1}^{\phi}.$ Clearly $Q_{k+1}^{\phi}$ consists of two copies $C_0^{(k)}$ and $C_1^{(k)}$ of $Q_{k}^{\phi}.$ For $i=0,1,$ let $U_k^{i}$ be the switch in the corresponding copy $C_i^{(k)}.$ It is then easy to observe that
\begin{equation*}
U_{k+1} = U_{k}^{0} \cup U_{k}^{1}.
\end{equation*}
This shows that the copies $C_0^{(k)}$ and $C_1^{(k)}$ in $Q_{k+1}^{\phi}$ exhibit canonical orientation after the switch with respect to $U_{k+1}.$ Further any arc between the two copies agrees with the canonical orientation (see Step 2(d) of Algorithm \ref{algnw1}). Hence the switch with respect to $U_{k+1}$ results in $Q_{k+1}^{\sigma}.$ Applying induction, the result follows.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{The skew spectrum of $H\Box G$ with $H$ bipartite}

In \cite{ABS}, Adiga et al. have shown that the skew energy of any oriented graph $G^{\phi}$ of order $n,$ for which the underlying undirected graph $G$ is $k$-regular, is bounded above by $n\sqrt{k}$ and posed the following problem:

\begin{problem}\label{np2}
Which $k$-regular graphs $G$ on $n$ vertices have orientations $\phi$ with $\mathcal{E}_S(G^{\phi})=n\sqrt{k},$ or equivalently, $S(G^{\phi})^TS(G^{\phi})=k I_n?$
\end{problem}

In this section, we give an orientation of the Cartesian product $H\Box G,$ where $H$ is bipartite, by extending the orientation of $P_m\Box G$ in \cite{CH}, and we calculate its skew spectrum. As an application of this orientation, we construct new families of oriented graphs with maximum skew energy, which generalizes the construction in \cite{CH}.

Let $H$ and $G$ be graphs with $p$ and $n$ vertices, respectively. Recall that the Cartesian product $H\Box G$ of $H$ and $G$ is the graph with vertex set $V(H) \times V(G)$ and the vertices $(u_1, v_1)$ and $(u_2, v_2)$ are adjacent in $H\Box G$ if and only if $u_1 = u_2$ and $v_1 v_2$ is an edge of $G,$ or if $v_1 = v_2$ and $u_1 u_2$ is an edge of $H.$ Assume that $\tau$ is any orientation of $H$ and $\phi$ is any orientation of $G.$ There is a natural way to define the oriented Cartesian product $H^{\tau} \Box G^{\phi}$ of $H^{\tau}$ and $G^{\phi}$ whose underlying undirected graph is $H\Box G:$ There is 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 $G^{\phi},$ or if $v_1 = v_2$ and $u_1 u_2$ is an arc of $H^{\tau}.$ The skew spectrum of $H^{\tau}\Box G^{\phi}$ has been determined in \cite{CH}. Some interesting results on the skew spectrum of the product $H^{\tau}\Box G^{\phi},$ where $H^{\tau}$ is an oriented hypercube are obtained in \cite{AB1}.

When $H$ is a bipartite graph with bipartition $X$ and $Y,$ we modify the above definition of $H^{\tau} \Box G^{\phi}$ to obtain a new product graph $(H^{\tau} \Box G^{\phi})^{o}$ with the following condition: If $u\in Y$ and $(v_1, v_2)\in \Gamma(G^{\phi}),$ then we make $(u,v_2) (u,v_1)$ an arc of $H^{\tau} \Box G^{\phi}$ (instead of $(u,v_1) (u,v_2)$); the other arcs of $H^{\tau} \Box G^{\phi}$ remain unchanged.

\begin{theorem}\label{5t8}
Let $H^{\tau}$ be an oriented bipartite graph of order $p$ and let the skew eigenvalues of $H^{\tau}$ be the nonzero complex numbers $\pm {\bf{i}}\mu_1, \pm {\bf{i}}\mu_2, \ldots, \pm {\bf{i}}\mu_{r}$ and $p-2r$ $0$'s. Let $G^{\phi}$ be an oriented graph of order $n$ and let the skew eigenvalues of $G^{\phi}$ be the nonzero complex numbers $\pm {\bf{i}}\lambda_1, \pm {\bf{i}}\lambda_2, \ldots, \pm {\bf{i}}\lambda_{t}$ and $n-2t$ $0$'s. Then the skew eigenvalues of the oriented graph $(H^{\tau} \Box G^{\phi})^{o}$ are $\pm {\bf{i}} \sqrt{\mu_{j}^{2}+\lambda_{k}^{2}},$ $j=1, \ldots, r,$ $k = 1, \ldots, t,$ each with multiplicity $2;$ $\pm {\bf{i}} \mu_j,$ $j=1, \ldots, r,$ each with multiplicity $n-2t;$ $\pm {\bf{i}} \lambda_j,$ $k=1, \ldots, t,$ each with multiplicity $p-2r$ and $0$ with multiplicity $(p-2r)(n-2t).$
\end{theorem}
\begin{proof}
Let $H=H(X,Y)$ with $|X|=p_1$ and $|Y|=p_2.$ With suitable labeling of the vertices of $H\Box G,$ the skew adjacency matrix $S=S((H^{\tau} \Box G^{\phi})^{o})$ can be chosen as follows:
\[
S = I'_{p_1+p_2} \otimes S(G^{\phi}) + S(H^{\tau}) \otimes I_n,
\]
where $I'_{p_1+p_2}=I'_p= (a_{ij}),$ $a_{ii} = 1$ if $1\leq i\leq p_1,$ $a_{ii} = -1$ if $p_1+1\leq i\leq p$ and $a_{ij}=0$ otherwise; $S(H^{\tau})$ is the partitioned matrix $\left(
          \begin{array}{cc}
            0 & B \\
            -B^T & 0 \\
          \end{array}
\right),$ where $B$ is a $p_1\times p_2$ matrix. Further, $\otimes$ stands for the Kronecker product of two matrices \cite{RB2}.

We first determine the singular values of $S.$ Note that the matrices $S,$ $S(H^{\tau})$ and $S(G^{\phi})$ are all skew symmetric. By calculation, we have
\begin{align}
\nonumber SS^T =& [I'_{p} \otimes S(G^{\phi}) + S(H^{\tau}) \otimes I_n] [I'_{p} \otimes (-S(G^{\phi})) + (-S(H^{\tau})) \otimes I_n]\\
\nonumber =& - [(I_{p} \otimes S^2(G^{\phi}) + S^2(H^{\tau}) \otimes I_n) + (I'_{p} \otimes S(G^{\phi}))(S(H^{\tau}) \otimes I_n)\\
\nonumber &  + (S(H^{\tau}) \otimes I_n) (I'_{p} \otimes S(G^{\phi}))].
\end{align}

Define $\omega_i=1$ for $i=1,2,\ldots, p_1$ and $\omega_i = -1$ for $i=p_1+1, p_1+2, \ldots, p.$ Denote $P^{(1)}= (I'_{p_1+p_2} \otimes S(G^{\phi})) (S(H^{\tau}) \otimes I_n)$ and $P^{(2)} = (S(H^{\tau}) \otimes I_n) (I'_{p_1+p_2} \otimes S(G^{\phi})).$ Note that $P^{(1)}$ and $P^{(2)}$ are both partitioned matrices each of order $p_1\times p_2$ in which each entry is an $n \times n$ submatrix. The $(i,j)^{\textnormal{th}}$ block in the matrix $P^{(1)}+P^{(2)}$ is given by
\[
P_{ij}^{(1)} + P_{ij}^{(2)} = S(H^{\tau})_{ij} S(G^{\phi}) (\omega_i + \omega_j).
\]

For any $1\leq i,$ $j \leq p,$ if $S(H^{\tau})_{ij}=0,$ then $P_{ij}^{(1)} + P_{ij}^{(2)}=0.$ Otherwise the vertices corresponding to $i$ and $j$ in $H^{\tau}$ are in different parts of the bipartition. That is, $1\leq i\leq p_1,$ $p_1+1\leq j\leq p$ or $1\leq j\leq p_1,$ $p_1+1\leq i\leq p.$ Then $\omega_i + \omega_j = 0.$ Thus it follows that $P^{(1)} + P^{(2)}=0.$ Hence
\[
SS^T = - (I_{p_1+p_2} \otimes S^2(G^{\phi}) + S^2(H^{\tau}) \otimes I_n).
\]

Therefore (cf. \cite{RB2}), the eigenvalues of $SS^T$ are $\mu(H^{\tau})^2+ \lambda(G^{\phi})^2,$ where ${\bf{i}}\mu(H^{\tau}) \in Sp_S(H^{\tau})$ and ${\bf{i}} \lambda(G^{\phi}) \in Sp_S(G^{\phi})$ and hence the eigenvalues of $S$ are of the form\\ $\pm {\bf{i}} \sqrt{\mu(H^{\tau})^2+ \lambda(G^{\phi})^2}.$ Thus the skew spectrum of $(H^{\tau} \Box G^{\phi})^{o}$ is as given in the statement of the theorem. The proof is thus complete.
\end{proof}

As an application of Theorem \ref{5t8}, we now construct a new family of oriented graphs with maximum skew energy.

\begin{theorem}\label{5t9}
Let $H^{\tau}$ be an oriented $\ell$-regular bipartite graph on $p$ vertices with maximum skew energy $\mathcal{E}_S(H^{\tau}) = p\sqrt{\ell}$ and $G^{\phi}$ be an oriented $k$-regular bipartite graph on $n$ vertices with maximum skew energy $\mathcal{E}_S(G^{\phi}) = n\sqrt{k}.$ Then the oriented graph $(H^{\tau} \Box G^{\phi})^{o}$ of $H\Box G$ has the maximum skew energy $\mathcal{E}_S((H^{\tau} \Box G^{\phi})^{o}) = np \sqrt{\ell + k}.$
\end{theorem}
\begin{proof}
Since $H^{\tau}$ and $G^{\phi}$ have maximum skew energy, $S(H^{\tau}) S(H^{\tau})^T= \ell I_p$ and $S(G^{\phi})$ $S(G^{\phi})^T$ $ = k I_n.$ Then the skew eigenvalues of $H^{\tau}$ are all $\pm {\bf{i}} \sqrt{\ell}$ and the skew eigenvalues of $G^{\phi}$ are all $\pm {\bf{i}} \sqrt{k}.$ By Theorem \ref{5t8}, all the skew eigenvalues of $(H^{\tau} \Box G^{\phi})^{o}$ are of the form $\pm {\bf{i}} \sqrt{\ell+k}$ and hence its skew energy is $np \sqrt{\ell + k},$ the maximum possible skew energy that an $(\ell+k)$-regular graph on $np$ vertices can have.
\end{proof}

An immediate corollary of Theorem \ref{5t9} is the following result of Cui and hou \cite{CH}.

\begin{corollary}\label{5c2}
Let $G^{\phi}$ be an oriented $k$-regular graph on $n$ vertices with maximum skew energy $\mathcal{E}_S(G^{\phi}) = n\sqrt{k}.$ Then the oriented graph $(P_2 \Box G^{\phi})^{o}$ of $P_2 \Box G$ has maximum skew energy $\mathcal{E}_S((P_2 \Box G^{\phi})^{o}) = 2n\sqrt{k+1}.$
\end{corollary}

Adiga et al. \cite{ABS} showed that a $1$-regular connected graph that has an orientation with maximum skew energy is $K_2;$ while a $2$-regular connected graph has an orientation with maximum skew energy if and only if it is an oddly oriented cycle $C_4.$ Tian \cite{T} proved that there exists a $k$-regular graph with $n= 2^k$ vertices having an orientation $\psi$ with maximum skew energy. Cui and Hou \cite{CH} constructed a $k$-regular graph of order $n = 2^{k-1}$ having an orientation $\varphi$ with maximum skew energy. The following examples provide new families of oriented graphs with fewer vertices that have maximum skew energy.

\begin{example}\label{5ex1}
Let $G_1 = K_{4,4}.$ For each $r\geq 2,$ set $G_r = K_{4,4} \Box G_{r-1}.$ As there is an orientation of $K_{4,4}$ with maximum skew energy $16$ (see {\emph{\cite{CLL}}}), for each $r\geq 1,$ there exists an orientation of $G_r$ that yields the maximum skew energy $2^{3r} \sqrt{4r}.$ This provides a family of $4r$-regular graphs of order $n = 2^{3r}$ each having an orientation with skew energy $2^{3r} \sqrt{4r},$ $r\geq 1.$
\end{example}

\begin{example}\label{5ex2}
Let $G_1 = K_4.$ For each $r\geq 2,$ set $G_r = K_{4,4} \Box G_{r-1}.$ Since there exist orientations for $K_4$ with maximum skew energy $4\sqrt{3}$ (see {\emph{\cite{ABS,GX}}}), the skew energy of $G_r,$ $r\geq 1,$ is $2^{3r-1}\sqrt{4r-1}$ and it is maximum. This provides a family of $4r-1$-regular graphs of order $2^{3r-1}$ each having an orientation with maximum skew energy $2^{3r-1} \sqrt{4r-1},$ $r\geq 1.$
\end{example}

\begin{example}\label{5ex3}
A new family of $4r-2$-regular oriented graphs of order $2^{3r-1}$ with maximum skew energy $2^{3r-1}\sqrt{4r-2},$ $r\geq 1$ is obtained when we set $G_1 = C_4$ in place of $K_4$ in Example $\ref{5ex2}.$
\end{example}

\begin{example}\label{5ex4}
A new family of $4r-3$-regular oriented graphs of order $2^{3r-2}$ with maximum skew energy $2^{3r-2}\sqrt{4r-3},$ $r\geq 1$ is obtained when we set $G_1 = P_2$ in place of $K_4$ in Example $\ref{5ex2}.$
\end{example}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgement} For the first two authors, this research was supported by the Department of Science and Technology, Government of India grant DST:SR/S4/MS:492, dated April 16, 2009. For the third, fourth and fifth authors, this research was supported by NSFC and the ``973'' program.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{20}
\bibitem{ABS}
C.~Adiga, R.~Balakrishnan, and Wasin So. \newblock The skew energy of a digraph. \newblock {\em Linear Algebra Appl.}, 432:1825--1835, 2010

\bibitem{AB1}
A.~Anuradha, and R.~Balakrishnan. \newblock Skew spectrum of the Cartesian product of an oriented graph with an oriented hypercube. \newblock In {\em Combinatorial Matrix Theory and Generalized Inverses of Matrices}, Eds. R.~B.~Bapat, S.~J.~Kirkland, K.~M.~Prasad, S.~Puntanen, pages 1--12. Springer, 2013.

\bibitem{RB2}
R.~Balakrishnan, and K.~Ranganathan. \newblock {\em A Textbook of Graph Theory}. \newblock Second Edition, Springer, New York (2012).

\bibitem{SK}
M.~Cavers, S.~M.~Cioab\u{a}, S.~Fallat, D.~A.~Gregory, W.~H.~Haemers, S.~J.~Kirkland, J.~J.~McDonald, and M.~Tsatsomeros. \newblock Skew-adjacency matrices of graphs. \newblock {\em Linear Algebra Appl.}, 436:4512--4529, 2012.

\bibitem{CLL}
X.~Chen, X.~Li, and H.~Lian. \newblock $4$-Regular oriented graphs with optimum skew energy. \newblock {\em Linear Algebra Appl.}, 439(10):2948--2960, 2013.

\bibitem{CH}
D.~Cui, and Y. Hou. \newblock On the skew spectra of Cartesian products of graphs. \newblock {\em The Electronic J. Combin.}, 20(2):\#P19, 2013.

\bibitem{GX}
S.~Gong, and G.~Xu. \newblock $3$-Regular digraphs with optimum skew energy. \newblock {\em Linear Algebra Appl.}, 436:465--471, 2012.

\bibitem{Gut78}
I.~Gutman. \newblock The energy of a graph. \newblock {\em Ber. Math. Statist. sekt. Forschungsz. Graz.}, 103:1--22, 1978.

\bibitem{GLZ}
I.~Gutman, X.~Li, and J.~Zhang. \newblock Graph Energy. \newblock In {\em Analysis of Complex Network: From Biology to Linguistics}, Eds. M.~Dehmer, and F.~Emmert-Streib, pages 145--174. Wiley-VCH Verlag, Weinheim, 2009.

\bibitem{HL}
Y.~Hou, and T.~Lei. \newblock Characteristic polynomials of skew-adjacency matrices of oriented graphs. \newblock {\em The Electronic J. Combin.}, 18:\#156, 2011.

\bibitem{LL}
X.~Li, and H.~Lian. \newblock A survey on the skew energy of oriented graphs. Available at \arxiv{1304.5707}

\bibitem{LSG}
X.~Li, Y.~Shi, and I.~Gutman. \newblock {\em Graph Energy}. \newblock Springer, New York, 2012.

\bibitem{SS}
B.~Shader, and Wasin So. \newblock Skew spectra of oriented graphs. \newblock {\em The Electronic J. Combin.}, 16:1--6, 2009.

\bibitem{T}
G-X.~Tian. \newblock On the skew energy of orientations of hypercubes. \newblock {\em Linear Algebra Appl.}, 435:2140--2149, 2011.

\end{thebibliography}

\end{document} 