\section{Introduction}
Let $n$ be a positive integer and $[n] \ceq \{1,\ldots,n\}$. Suppose that ${\mathcal{G}}=\bigl([n],E\bigr)$ is a simple graph. We associate an edge $e=\{i,j\} \in E$ with the transposition $\tau_e \ceq (i\,j) \in \mathfrak{S}_n$, where $\mathfrak{S}_n$ denotes the symmetric group of degree $n$. 
D\'enes proved the following theorem.

\begin{theorem}[D\'enes \cite{denes1959representation-potmiothaos}. See also \cite{moszkowski1989solution-ejoc},  \cite{pawlowski2022chromatic-ac}]\label{t1}
\textit{Let $\mathcal{G}=\bigl([n],E\bigr)$ be a simple graph. The product $\tau_{e_m}\cdots\tau_{e_1}$ is an $n$-cycle for any linear order $(e_1,\ldots,e_m)$ on $E$ if and only if $\mathcal{G}$ is a tree.}
\end{theorem}

As a corollary, D\'enes also proved the following claim.


\begin{corollary}[D\'enes \cite{denes1959representation-potmiothaos}]
\textit{The number of representations of a $n$-cycle by means of product of $n-1$ transpositions is $n^{n-2}$.}
\end{corollary}

We will extend Theorem $\ref{t1}$ for the hyperoctahedral group $\mathfrak{H}_n$. Since it is known that $\mathfrak{S}_n$ is a Weyl group of the root system of type $A_{n-1}$ and $\mathfrak{H}_n$ is a Weyl group of the root system of type $B_n$, It is a natural idea to consider this extension.

Let $I_n \ceq \{-n,\ldots,-1,1,\ldots,n\}$. The \textit{hyperoctahedral group} $\mathfrak{H}_n$ is a subgroup of the symmetric group $\mathfrak{S}_{I_n}$ of $I_n$, defined by 
\[
\mathfrak{H}_n \ceq \bigset{\eta \in \mathfrak{S}_{I_n}}{\text{$\eta(-i)=-\eta(i)$ for all $i \in [n]$}}.
\]
An element $\eta \in \mathfrak{H}_n$, called a \textit{signed permutation}, is expressed as follows:
\[
\eta=\begin{pmatrix}
1&2&\cdots&n\\
\eta_1&\eta_2&\cdots&\eta_n
\end{pmatrix},
\]
where $\eta_1,\ldots,\eta_n \in I_n$ have different absolute values. In particular, given a permutation in $\mathfrak{S}_n$, the signed permutation in $\mathfrak{H}_n$ is naturally determined. Thus we can consider $\mathfrak{S}_n$ to be a subgroup of $\mathfrak{H}_n$.

There are three types of \textit{transpositions} in $\mathfrak{H}_n$. For $i,j$ be distinct numbers in $[n]$ and $\epsilon$ be a sign $+$ or $-$, we say that
\[
(i\ \epsilon j) \ceq \begin{pmatrix}
1&\cdots&i&\cdots&j&\cdots&n\\
1&\cdots&\epsilon j&\cdots&\epsilon i&\cdots&n
\end{pmatrix}
\]
is a \textit{positive transposition} if $\epsilon=+$ and a \textit{negative transposition} if $\epsilon=-$.  Note that we can consider a positive transposition as a transposition in $\mathfrak{S}_n$. For $i \in [n]$, we say that
\[
(i\,{-i}) \ceq \begin{pmatrix}
1&\cdots&i&\cdots&n\\
1&\cdots&{-i}&\cdots&n
\end{pmatrix}
\]
is an \textit{inversion transposition}.


A signed permutation is decomposed uniquely into a product of commuting signed cycles. For $i_1,\ldots,i_l$ be distinct numbers in $[n]$ and $\epsilon_1,\ldots,\epsilon_l \in \{+,-\}$, which we consider as a multiplicative group of order two in the natural way, given such a \textit{signed cycle} of size $l$
\[
\sigma=\begin{pmatrix}
i_1&i_2&\cdots&i_{l-1}&i_l\\
\epsilon_1i_2&\epsilon_2i_3&\cdots&\epsilon_{l-1}i_l&\epsilon_li_1
\end{pmatrix},
\]
we say that $\sigma$ is an \textit{even $l$-cycle} if $\epsilon_1\cdots\epsilon_l=+$ and an \textit{odd $l$-cycle} if $\epsilon_1\cdots\epsilon_l=-$. In addition, we denote 
\[
\sigma=\bigl(i_1\ \epsilon_1i_2\ (\epsilon_1\epsilon_2)i_3\ \cdots\cdots\ (\epsilon_1\cdots\epsilon_{l-1})i_l\bigr)_{\epsilon_1\cdots\epsilon_l}.
\]
Sometimes, $\sigma$ is written as
\[
\sigma=\bigl({-}i_1\ {-}\epsilon_1i_2\ {-}(\epsilon_1\epsilon_2)i_3\ \cdots\cdots\ {-}(\epsilon_1\cdots\epsilon_{l-1})i_l\bigr)_{\epsilon_1\cdots\epsilon_l}.
\]
Note that we see that
\[
(i\,j)_+=(i\,j),\quad (i\,j)_- \neq (i\,{-j}),\quad (i)_-=(i\,{-i}).
\]


The \textit{cycle type} of the signed permutation $\eta$ is the pair of partitions $(\lambda,\mu)$, where
$\lambda$ (resp\priod $\mu$) is the integer partition consisting of the length of even (resp\priod odd) cycles appearing in the decomposition of $\eta$.
For example, if
\[
\eta \ceq \begin{pmatrix}
1&2&3&4&5&6&7&8\\
-5&4&-3&2&-8&7&-6&1
\end{pmatrix} \in \mathfrak{H}_8,
\]
then
\[
\eta = (1\ {-}5\  8)_+(2\ 4)_+(3)_-(6\ 7)_-
\]
and the cycle type of $\eta$ is $\bigl((3,2),\, (2,1)\bigr)$. 

The cycle type of an even $n$-cycle is $\bigl((n),0\bigr)$ and that of an odd $n$-cycle is $\bigl(0,(n)\bigr)$. Note that two signed permutations have the same cycle type if and only if they are conjugate.


We introduce the signed graph to consider an analogy of D\'enes' results for $\mathfrak{H}_n$. Here, define a \textit{signed graph} as a quadruple $\mathcal{G}=\bigl([n],E^+,E^-,L\bigr)$, where $E^+$ and $E^-$ are collections consisting of unordered pairs of elements in $[n]$, and $L$ is a subset of $[n]$. An element in $[n]$ is called a \textit{vertex}, an element in $E^+$ (resp\priod $E^-$) is called a \textit{positive} (resp\priod \textit{negative}) \textit{edge}, and an element in $L$ is called a \textit{loop}. A signed graph $\mathcal{G}$ is a \textit{signed tree} (resp\priod \textit{cycle}) if $E^+ \cap E^-=L=\emptyset$ and the underlying simple graph $\bigl([n],E^+ \cup E^-\bigr)$ is a tree (resp\priod cycle). Let $E \ceq E^+ \sqcup E^- \sqcup L$. For every $e \in E$, define a transposition $\tau_e \in \mathfrak{H}_n$ by
\[
\tau_e \ceq \begin{cases}
(i\ {j})&\text{if } e=\{i,j\} \in E^+,\\
(i\ {-j})&\text{if } e=\{i,j\} \in E^-,\\
(i\ {-i})&\text{if } e=i \in L.
\end{cases}
\]
The main results are as follows:

\begin{theorem}\label{t2}
\textit{Let $\mathcal{G}=\bigl([n],E^+,E^-,L\bigr)$ be a  signed graph. Then the following two claims hold:
\begin{enumerate}[(A)]
\item The product $\tau_{e_m}\cdots\tau_{e_1}$ is an even $n$-cycle for any linear order $(e_1,\ldots,e_m)$ on $E$ if and only if $\mathcal{G}$ is a signed tree with an even number of loops;\label{t211}
\item The product $\tau_{e_m}\cdots\tau_{e_1}$ is an odd $n$-cycle for any linear order $(e_1,\ldots,e_m)$ on $E$ if and only if $\mathcal{G}$ is a signed tree with an odd number of loops.\label{t221}
\end{enumerate}}
\end{theorem}



\begin{corollary}\label{c4}
\textit{
\begin{enumerate}[(A)]
\item The number of representations of an even $n$-cycle by means of product of $n-1$ transpositions is $n^{n-2}$;
\item The number of representations of an odd $n$-cycle by means of product of $n$ transpositions is $n^n$.
\end{enumerate}}
\end{corollary}

{For Corollary $\ref{c4}$, a more general claim is already known (see \cite[Theorem 7.5]{bessis2015finite-aom} and below for example). In this paper, we prove Corollary $\ref{c4}$ by counting the number of sequences consisting of $n-1$ (resp\priod $n$) of transpositions such that the product is an even (resp\priod odd) $n$-cycle. }

The organization of this paper is as follows.
In Section $\ref{sec2}$, we prove the special case of Theorem $\ref{t2}$.
In Section $\ref{sec3}$. we prove Theorem $\ref{t2}$ and Corollary $\ref{c4}$.

\section{Signed graphs without loops and 2-cycle graphs} \label{sec2}
First, we review the properties of transpositions and signed cycles in $\mathfrak{H}_n$ necessary for the proof of Theorem $\ref{t2}$. We do not prove the following two lemmas since their proofs are easy.

\begin{lemma}\label{l1}
\textit{Let $i,j,k \in [n]$ be distinct integers.  Then the following three claims hold:
\begin{enumerate}[(i)]
\item $(i\ {-j})=(i\ {-i})(j\ {-j})(i\ {j})$; \label{l11}
\item $(i\ {j})(j\ {-j})=(i\ {-i})(i\ {j})$; \label{l12}
\item $(i\ {j})(k\ {-k})=(k\ {-k})(i\ {j})$. \label{l13}
\end{enumerate}
In particular, every signed permutation in $\mathfrak{H}_n$ is represented by the product of some inversion transpositions and the product of some positive transpositions.}
\end{lemma}




\begin{lemma}\label{l2}
\textit{Suppose that $i_1,\ldots,i_l \in I_n$ have different absolute values and $\epsilon \in \{+,-\}$.  Then the following two claims hold:
\begin{enumerate}[(i)]
\item $(i_1\ i_2\ \cdots\ i_l)_\epsilon=(i_2\ \cdots\ i_l\ \epsilon i_1)_\epsilon$; \label{}
\item $(i_1\,{-i_1})(i_1\ \cdots\ i_l)_\epsilon=(i_1\ \cdots\ i_l)_{-\epsilon}$. \label{}
\end{enumerate}
In particular, the product of an even (resp\priod odd) $n$-cycle and an inversion transposition is an odd  (resp\priod even) $n$-cycle.}
\end{lemma}



Before the proof of Theorem $\ref{t2}$, as a special case, assume that a signed graph $\mathcal{G}=\bigl([n],E^+,E^-,L\bigr)$ has no 2-cycle graphs and $L=\emptyset$, where a 2-cycle graph is a signed graph on two vertices with a positive edge and a negative edge joining them. 
{For $e \in E^+ \cup E^-$, define $\tau'_e \in \mathfrak{S}_n \subset \mathfrak{H}_n$ as the positive transposition exchanging the endvertices of $e$.}
\begin{lemma}\label{l23}
{\textit{Let $\mathcal{G}=\bigl([n],E^+,E^-,L\bigr)$ be a signed graph without 2-cycle graphs and $L=\emptyset$. Then 
\begin{enumerate}[(i)]
\item For a linear order $(e_1,\ldots,e_m)$ on $E$, the product $\tau_{e_m}\cdots\tau_{e_1}$ is an even $n$-cycle if and only if the product $\tau_{e_m}'\cdots\tau_{e_1}'$ is an even $n$-cycle; \label{i3}
\item For any linear order $(e_1,\ldots,e_m)$ on $E$, the product $\tau_{e_m}\cdots\tau_{e_1}$ is not an odd $n$-cycle.\label{ii3}
\end{enumerate}}}
\end{lemma}
\begin{proof}
{For a linear order $(e_1,\ldots,e_m)$ on $E$, let $\eta \ceq \tau_{e_m}\cdots\tau_{e_1}$ and $\eta' \ceq \tau_{e_m}'\cdots\tau_{e_1}'$. If $e_i \in E^-$, then the negative transposition $\tau_{e_i}$ is represented as the product of two invertion transpositions and the positive transposition $\tau_{e_i}'$ by Lemma $\ref{l1}$ $\eqref{l11}$. Then we get
\begin{align}
\eta =\nu_1\cdots \nu_s\cdot \eta' \label{ss1}
\end{align}
by Lemma $\ref{l1}$ $\eqref{l12}$ and $\eqref{l13}$, where $\nu_1,\ldots,\nu_s$ are inversion transpositions and $s=2|E^-|$. Hence $\eqref{i3}$ is true by Lemma $\ref{l2}$.}

{Assume that the product $\tau_{e_m}\cdots\tau_{e_1}$ is an odd $n$-cycle for some linear order $(e_1,\ldots,e_m)$ on $E$. By Lemma $\ref{l2}$ and the equality $\eqref{ss1}$, we obtain that the product $\tau_{e_m}'\cdots\tau_{e_1}'$ is also an odd $n$-cycle, which is a contradiction to the fact that $\tau_{e_m}'\cdots\tau_{e_1}' \in \mathfrak{S}_n$. Therefore $\eqref{ii3}$ is true.}
\end{proof}

The proof in this case follows from Theorem $\ref{t1}$.

\begin{theorem}\label{t3}
\textit{Let $\mathcal{G}=\bigl( [n],E^+,E^-,L\bigr)$ be a signed graph without 2-cycle graphs and $L=\emptyset$. The product $\tau_{e_m}\cdots \tau_{e_1}$ is an even $n$-cycle for any linear order $(e_1,\ldots,e_m)$ on $E$ if and only if $\mathcal{G}$ is a signed tree.}
\end{theorem}
\begin{proof}
Define a simple graph $\bar{\mathcal{G}}=\bigl([n],\bar{E}\bigr)$, where $\bar{E}=E^+ \cup E^-$. Since $\mathcal{G}$ has no loops and 2-cycle graphs, $\mathcal{G}$ is a signed tree if and only if $\bar{\mathcal{G}}$ is a tree. Since $\mathcal{G}$ has no 2-cycle graphs, a linear order on $\bar{E}$ determines naturally a linear order on $E$, and vice versa. 



Suppose that the product $\tau_{e_m}\cdots \tau_{e_1}$ is an even $n$-cycle for any linear order $(e_1,\ldots,e_m)$ on $E$. By Lemma $\ref{l23}$, the product $\tau_{e_m}'\cdots \tau_{e_1}'$ is an $n$-cycle for any linear order on $\bar{E}$. Therefore we get that $\bar{\mathcal{G}}$ is a tree by Theorem $\ref{t1}$. Thus $\mathcal{G}$ is a signed tree. The proof of the converse is similar.
\end{proof}

\section{Proof of Theorem 1.3 and Corollary 1.4}\label{sec3}

First, we prove the following a claim necessary for the proof of Theorem $\ref{t2}$.
\begin{lemma}\label{l3}
\textit{Let $\mathcal{G}=\bigl([n],E^+,E^-,L\bigr)$ be a signed graph. If $\mathcal{G}$ has a cycle (including 2-cycle graph), then there exists a linear order $(e_1,\ldots,e_m)$ on $E$ such that the product $\tau_{e_m}\cdots\tau_{e_1}$ is neither an even $n$-cycle nor an odd $n$-cycle.}
\end{lemma}
\begin{proof}
Let $\gamma$ be a minimal cycle of $\mathcal{G}$ with vertices $\{v_1,\ldots,v_r\}$, edges $\{c_1,\ldots,c_r\}$, where $c_i$ connects $v_i$ and $v_{i+1}$ for all $1 \leq i \leq r-1$ and $c_r$ connects $v_r$ and $v_1$. 



Let $\{b_1,\ldots,b_s\}$ be the set of edges of $\mathcal{G}$ incident to $v_r$ except $c_r$ and $c_1$. Suppose that $d_1,\ldots,d_t$ are the other edges of $\mathcal{G}$. Then
\[
E =\{c_1,\ldots,c_r,b_1,\ldots,b_s,d_1,\ldots,d_t\}.
\]
Define
\[
\eta \ceq \tau_{b_1} \cdots \tau_{b_s}\tau_{c_r}\tau_{d_1}\cdots\tau_{d_t}\tau_{c_{r-1}}\cdots\tau_{c_1}.
\] 
We obtain
\begin{align}
(\tau_{c_{r-1}}\cdots\tau_{c_1})(v_1)=\epsilon\cdot v_r, \label{s2}
\end{align}
where $\epsilon  \in \{+,-\}$. For all $1 \leq i \leq t$, since $d_i$ is not incident to $v_r$,
\begin{align}
\begin{aligned}
(\tau_{c_r}\tau_{d_1}\cdots\tau_{d_t}\tau_{c_{r-1}}\cdots\tau_{c_1})(v_1) &= (\tau_{c_r}\tau_{d_1}\cdots\tau_{d_t})(\epsilon\cdot v_r)\\
&=\tau_{c_r}(\epsilon \cdot v_r)\\
&=\epsilon'\epsilon\cdot v_1
\end{aligned}\label{s3}
\end{align}
by $\eqref{s2}$, where $\epsilon'$ is a sign of the edge $c_s$.

Assume that there exists $j_0$ such that $b_{j_0}$ is an edge incident to $v_1$. Since edges $b_{j_0}$ and $c_r$ form a 2-cycle graph, $r=2$ by the minimality of $\gamma$. Then edges $c_1$ and $c_r$ form a 2-cycle graph. Thus we get $c_1=b_{j_0}$, which is a contradiction. Therefore we know that $b_j$ is not incident to $v_1$ for any $1 \leq j \leq s$. Hence
\begin{align}
\begin{aligned}
\eta(v_1) &= (\tau_{b_1} \cdots \tau_{b_s}\tau_{c_r}\tau_{d_1}\cdots\tau_{d_t}\tau_{c_{r-1}}\cdots\tau_{c_1})(v_1)\\
&= (\tau_{b_1} \cdots \tau_{b_s})(\epsilon'\epsilon\cdot v_1)\\
&= \epsilon'\epsilon\cdot v_1
\end{aligned}\label{s4}
\end{align}
by $\eqref{s3}$. The equality $\eqref{s4}$ indicates that $\eta$ is neither an even $n$-cycle nor an odd $n$-cycle.
\end{proof}

\begin{figure}[h]
\begin{tikzpicture}
\node (0) at (-8.3,0) {};
\node(00) at (0,0) {$\gamma$};
\node[v] (1) at (-1.3,1.3) {};
\node[v] (2) at (0,2.6) {};
\node[v] (3) at (1.3,1.3) {};
\node[v] (4) at (2.6,0) {};
\coordinate (5) at (1.3,-1.3) {};
\coordinate (7) at (-1.3,-1.3) {};
\node[v] (8) at (-2.6,0) {};
\draw[dashed] (5) -- (7) -- node[below left]{$c_{r-1}$} (8) (4) -- node[below right]{$c_4$} (5);
\draw (8) node[left]{$v_r$} -- node[above=5pt, left=-2pt]{$c_r$} (1) node[below=8pt,right=-4pt]{$v_1$} -- node[below right]{$c_1$} (2) node[above]{$v_2$} --node[above=5pt, right=-2pt]{$c_2$} (3) node[below left]{$v_3$} -- node[above=5pt, right=-2pt]{$c_3$} (4) node[below right]{$v_4$};
\node[v] (a) at (-3.2,1.8) {};
\node[v] (aa) at (-2,3) {};
\node[v] (b) at (-4,3.2) {};
\node[v] (c) at (4,1.3) {};
\draw (b) -- node[left]{$d_1$} (a) -- node[above]{$b_1$} (1) -- node[right]{$b_2$} (aa);
\draw (c) -- node[below=5pt, right=-2pt]{$d_2$} (4);
\end{tikzpicture}
\caption{A graph in Lemma $\ref{l3}$.}
\label{f1}
\end{figure}




Now, we are ready to prove Theorem $\ref{t2}$. 
\begin{theorem}[Restatement of Theorem $\ref{t2}$]\label{t32}
\textit{Let $\mathcal{G}=\bigl([n],E^+,E^-,L\bigr)$ be a  signed graph. Then the following two claims hold:
\begin{enumerate}[(A)]
\item The product $\tau_{e_m}\cdots\tau_{e_1}$ is an even $n$-cycle for any linear order $(e_1,\ldots,e_m)$ on $E$ if and only if $\mathcal{G}$ is a signed tree with an even number of loops;\label{t21}
\item The product $\tau_{e_m}\cdots\tau_{e_1}$ is an odd $n$-cycle for any linear order $(e_1,\ldots,e_m)$ on $E$ if and only if $\mathcal{G}$ is a signed tree with an odd number of loops.\label{t22}
\end{enumerate}}
\end{theorem}





\begin{proof}
We will show only $\eqref{t21}$ since $\eqref{t22}$ can be proved with a rewording of the proof of $\eqref{t21}$ slightly. 

Assume that the product determined by any linear order on $E$ is an even $n$-cycle. Let $\mathcal{G}'=\bigl([n],E^+,E^-,\emptyset\bigr)$ be a  signed graph obtained by removing loops from $\mathcal{G}$ and $E' \ceq E^+ \sqcup E^-$. By Lemma $\ref{l3}$, $\mathcal{G}$ and $\mathcal{G}'$ have no 2-cycles. We need to show that $\mathcal{G}'$ is a signed tree. 

Let $(e_1,\ldots,e_m)$ be a linear order on $E'$ and $\eta' \ceq \tau_{e_m}\cdots\tau_{e_1}$. Extending the linear order $(e_1,\ldots, e_m)$, we can obtain the linear order $C \ceq (e_1,\ldots, e_m, l_1,\ldots,l_s)$ on $E$, where $L=\{l_1,\ldots,l_s\}$. Suppose that $\eta$ is the product determined by $C$. Namely, 
\begin{align}
\eta=\tau_{l_s} \cdots\tau_{l_1}\cdot \eta'. \label{ss5}
\end{align}
Note that $\tau_{l_1},\ldots,\tau_{l_s}$ are inversion transpositions. By Lemma $\ref{l2}$, Lemma $\ref{l23}$, and the equality $\eqref{ss5}$, we obtain that $\eta'$ is an even $n$-cycle and $s$ is even since $\eta$ is an even $n$-cycle. Therefore we get that $\mathcal{G}'$ is a signed tree by Theorem $\ref{t3}$. Thus $\mathcal{G}$ is a signed tree with an even number of loops. The proof of the converse is similar. Theorem $\ref{t2}$ $\eqref{t21}$ is presented now.
\end{proof}


Next, we prove Corollary $\ref{c4}$. 
\begin{corollary}[Restatement of Corollary $\ref{c4}$]
\textit{
\begin{enumerate}[(A)]
\item The number of representations of an even $n$-cycle by means of product of $n-1$ transpositions is $n^{n-2}$;
\item The number of representations of an odd $n$-cycle by means of product of $n$ transpositions is $n^n$.
\end{enumerate}}
\end{corollary}
\begin{proof}
Let $N_A$ (resp\priod $N_B$) be the number of representations of an even (resp\priod odd) $n$-cycle by means of product of $n-1$ (resp\priod $n$) transpositions. Suppose that $W_A$ (resp\priod $W_B$) be the number of sequences consisting of $n-1$ (resp\priod $n$) transpositions such that the product is an even (resp\priod odd) $n$-cycle. There are $(n-1)!\cdot 2^{n-1}$ even (resp\priod odd) $n$-cycles since a signed $n$-cycle is denoted by $(1\ i_2\ i_3\ \cdots\ i_n)_\epsilon$ and a signed $n$-cycle is determined by sequence consisting $2,\ldots,n$ without repetition and sequence consisting $n-1$ signs. Thus we get
\begin{align}\label{s5}
W_A=(n-1)!\cdot 2^{n-1}\cdot N_A,\quad W_B=(n-1)!\cdot 2^{n-1}\cdot N_B.
\end{align}
On the other hand, the number of vertex-labeled trees with $n$ vertices is $n^{n-2}$ by Cayley's fomula.  By Theorem $\ref{t2}$, we know
\begin{align}\label{s6}
W_A=n^{n-2}\cdot 2^{n-1}\cdot (n-1)!,\quad W_B=n^{n-2}\cdot 2^{n-1}\cdot n\cdot n!.
\end{align}
Therefore we obtain 
\[
N_A=n^{n-2},\quad N_B=n^n
\]
by $\eqref{s5}$ and $\eqref{s6}$.
\end{proof}

\bibliographystyle{amsplain}
