# Hermitian adjacency matrices of mixed multigraphs ††thanks: This work was
supported by National Science Foundation of China (Grant No. 11901525,
12100557) and by Zhejiang Provincial Natural Science Foundation of China
(Grant No. LQ21A010004).

Bo-Jun Yuan Shaowei Sun Dijian Wang
School of Science, Zhejiang University of Science and Technology, Hangzhou
310023, PR China Corresponding author. E-mail address<EMAIL_ADDRESS>(D.-J. Wang<EMAIL_ADDRESS>(B.-J. Yuan<EMAIL_ADDRESS>(S.-W.
Sun).

###### Abstract

A mixed multigraph is obtained from an undirected multigraph by orienting a
subset of its edges. In this paper, we study a new Hermitian matrix
representation of mixed multigraphs, give an introduction to cospectral
operations on mixed multigraphs, and characterize switching equivalent mixed
multigraphs in terms of fundamental cycle basis. As an application, an upper
bound of cospectral classes of mixed multigraphs with the same underlying
graph is obtained.

Keywords: Mixed multigraph; Hermitian adjacency matrix; Switching equivalence;
Cospectral class.

##  1 Introduction

All graphs considered in this paper may contain multiple edges but no loops. A
mixed multigraph $M$ is obtained from an undirected multigraph $G$ by
orienting a subset of its edges, where $G$ is called the underlying graph of
$M$, written as $G(M)$. Formally, a mixed multigraph is an ordered triple
$(V,E,A)$, where $V$ is the vertex set, $E$ is the undirected edge set and $A$
is the directed edge (arc) set. We shall denote an edge with endpoints $u$ and
$v$ by $\\{u,v\\}$ if it is undirected, $(u,v)$ if it is directed from the
initial vertex $u$ to the terminal vertex $v$, and $uv$ if it is either
undirected or directed from $u$ to $v$. If $uv\in A$ and $vu\in A$, the pair
$\\{uv,vu\\}$ of these oppositely directed arcs is referred to as a digon of
$M$, denoted by $\\{u,v\\}$. A mixed multigraph can be viewed as a directed
graph (henceforth abbreviated as digraph) if we view each undirected edge as a
digon.

One basic problem in spectral graph theory is investigating the relation
between the eigenvalues of some matrix representation of a graph and its
structural properties. In the current setting, it is natural to consider
Hermitian matrices as the adjacency matrices of mixed graphs, in which two
conjugate complex numbers are used to reflect the directed information of an
edge. Based on this, Liu and Li [12] and independently by Guo and Mohar [7]
introduced the Hermitian adjacency matrix of the first kind for simple mixed
graphs, in which the $uv$-entry is $1$ if $\\{u,v\\}$ is undirected, is
$\mathsf{i}$ $(=\sqrt{-1})$ if $(u,v)$ is an arc, is $-\mathsf{i}$ if $(v,u)$
is an arc, and is $0$ otherwise. In recent years, the Hermitian spectrum of
simple mixed graphs has been the subject of several publications. One can
refer to the literature [2, 3, 6, 8, 15, 16, 19, 20] and the references
therein. However, it seems that this kind of Hermitian matrix with entries
from {0, 1, $\pm\mathsf{i}$} is more valid for simple mixed graphs. As such,
the entries of Hermitian matrices of mixed multigraphs (or digraphs) may need
to be restricted on a bigger algebra system. Mohar [14] provided an
interesting new choice as follows.

Let $D$ be a digraph with vertex set $V$ and arc set $A$. Let
$\alpha=a+b\mathsf{i}$ be a complex number satisfying $|\alpha|=1$ and $a\geq
0,$ and let $\bar{\alpha}=a-b\mathsf{i}$ be its conjugate. Mohar [14]
introduced the Hermitian adjacency matrix
$N^{\alpha}(D)=[N^{\alpha}_{uv}]\in\mathbb{C}^{V\times V}$ of $D$ with

$N^{\alpha}_{uv}=e(u,v)\alpha+e(v,u)\bar{\alpha},$

where $e(x,y)$ denotes the number of arcs directed from $x$ to $y.$

If we take $\alpha=\mathsf{i}=\sqrt{-1}$, then the corresponding entries of
$N^{\alpha}(D)$ are the Gaussian integers. In the current setting, digraphs
are maybe not in bijective correspondence with their matrices. For instance,
the matrix of digraph consisting of a digon is a null matrix of order 2, which
is the same as the matrix of digraph consisting of two isolated vertices.
Thus, in a sense, taking the primitive sixth root of unity
$\omega=\frac{1}{2}+\frac{\sqrt{3}}{2}\mathsf{i}$ as $\alpha$ may be the most
natural choice to characterize the interesting combinatorial structure of a
digraph (or a mixed multigraph) by its spectrum. Note that a digon has the
contribution 1 to the corresponding entries in $N^{\omega}$ because
$\omega+\overline{\omega}=1$, which can be naturally considered as the
contribution of an undirected edge if we view a digon as an undirected edge.
In addition, the entries of Hermitian adjacency matrix $N^{\omega}$ are
Eisenstein integers which play an important role in formal theory of linear
independence, see [4, 18]. It also seems to be associated with Quantum Field
Theory from theoretical physics [10].

Let us come back to the matrix representation of mixed multigraphs. We
emphasize here that since digons behave like undirected edges, for our
purposes throughout this paper, we may assume that there are no digons in
mixed multigraphs. Equivalently, for any two adjacent vertices $u$ and $v$,
the set of edges between $u$ and $v$ consists of undirected edges and arcs
with the same direction. In this way, the Hermitian adjacency matrix of a
mixed multigraph $M=(V,E,A)$ is defined as $N^{\omega}(M)=[N^{\omega}_{uv}]$
with

$N^{\omega}_{uv}=\left\\{\begin{array}[]{ll}e\\{u,v\\}&{\rm if\ there\ are\
only\ undirected\ edges\ between}\ u\ {\rm and}\ v;\\\
e\\{u,v\\}+e(u,v)\omega&{\rm if\ there\ are\ arcs\ directed\ from}\ u\ {\rm
to}\ v;\\\ e\\{u,v\\}+e(v,u)\overline{\omega}&{\rm if\ there\ are\ arcs\
directed\ from}\ v\ {\rm to}\ u;\\\ 0&{\rm otherwise,}\end{array}\right.$

where $e\\{x,y\\}$ denotes the number of undirected edges between vertices $x$
and $y$ and $e(x,y)$ denotes the number of arcs directed from $x$ to $y.$

Hereafter, we shall briefly denote $N(M)$ by the Hermitian adjacency matrix of
a mixed multigraph $M$ instead of the notation $N^{\omega}(M).$ Obviously,
$N(M)$ is a Hermitian matrix, and thus is diagonalizable with real
eigenvalues. The eigenvalues, the spectrum, and the characteristic polynomial
$\mathnormal{\Phi}(M,\lambda)$ of a mixed multigraph $M$ always refer to those
of its Hermitian adjacency matrix $N(M)$. Two mixed multigraphs $M$ and
$M^{\prime}$ are called cospectral if they have the same spectrum, and they
are called antispectral if for every eigenvalue $\lambda$ of $M$ of
multiplicity $\ell$, $-\lambda$ is an eigenvalue of $M^{\prime}$ with the same
multiplicity $\ell$.

The motivation for this paper is to study a new matrix representation of mixed
multigraphs. In Section 2, we give the expression of characteristic
polynomials of mixed multigraphs. In Section 3, we introduce some graphic
operations which can preserve the spectrum of mixed multigraphs via its new
Hermitian adjacency matrix. In Section 4, we characterize switching equivalent
mixed multigraphs in terms of fundamental cycle basis. As an application, an
upper bound of cospectral classes of mixed multigraphs with the same
underlying graph is obtained.

##  2 Preliminaries

###  2.1 Characteristic polynomials of mixed multigraphs

A mixed multigraph is called simple if its underlying graph is a simple graph.
It is said to be a mixed walk, mixed cycle, etc., if its underlying graph is a
walk, cycle, etc., respectively.

Let $M=(V,E,A)$ be a connected mixed multigraph and let $N(M)=[N_{uv}]$ be its
Hermitian adjacency matrix. For a mixed walk
$W=v_{1}e_{1}v_{2}e_{2}v_{3}\cdots v_{s-1}e_{s-1}v_{s}$ in $M$, the weight of
$W$ in $M$ is defined as

$wt(W)=N_{e_{1}}N_{e_{2}}\cdots N_{e_{s-1}},$ $None$

where, for each $i=1,2,\ldots,s-1$, $N_{e_{i}}=1$ if $e_{i}\in E$,
$N_{e_{i}}=\omega$ if $e_{i}\in A$ is directed from $v_{i}$ to $v_{i+1}$, and
$N_{e_{i}}=\overline{\omega}$ if $e_{i}\in A$ is directed from $v_{i+1}$ to
$v_{i}$. For a mixed cycle $C$, we need to assign a direction for $C$ before
calculating its weight. Since $N(M)$ is Hermitian, if for one direction the
weight of a mixed cycle is $\beta$, then for the reversed direction its weight
is $\bar{\beta}$ (the conjugate number of $\beta$). For a given cycle
direction of $C$, assume that $f$ ($b$, resp.) is the number of forward
(backward, resp.) arcs in $C$. Now we express
$\omega=\frac{1}{2}+\frac{\sqrt{3}}{2}\mathsf{i}$ in terms of trigonometric
function, that is, $\omega=\cos\theta+\mathsf{i}\sin\theta,$ where
$\theta=\pi/3.$ In doing so, we may obtain a concise expression for the
characteristic polynomial of $M$ below. We define the value of $C$ to be
$wt(C)+\overline{wt(C)}$, denoted by $\nu(C)$. It follows that

$\displaystyle\nu(C)$ $\displaystyle=$ $\displaystyle
wt(C)+\overline{wt(C)}=\omega^{f}\overline{\omega}^{b}+\overline{\omega}^{f}\omega^{b}=2{\rm
Re}(\omega^{f}\overline{\omega}^{b})$ $\displaystyle=$ $\displaystyle 2{\rm
Re}\left((\cos(f\theta)+\mathsf{i}\sin(f\theta))\cdot(\cos(b\theta)-\mathsf{i}\sin(b\theta))\right)$
$\displaystyle=$ $\displaystyle 2\cos((f-b)\theta)=2\cos((f-b)\pi/3).$

Since $\nu(C)=2\cos((f-b)\theta)=2\cos((b-f)\theta)$, the value of an
arbitrary mixed cycle $C$ is independent of the chosen direction of $C$.

Note that any mixed cycle $C$ satisfies $\nu(C)\neq 0$ as $f$ and $b$ in $C$
are non-negative integers (see Observation 2.2). A subgraph of $M$ whose each
component is an (undirected or directed) edge or a mixed cycle (including the
mixed cycle of length $2$) is referred to as a Sachs subgraph of $M$. We
emphasize here that a single edge can not be enumerated as a mixed cycle of
length $2$ when we consider the computation of characteristic polynomial of a
mixed multigraph.

The following theorem can be considered as an analogue of Sachs’ Coefficient
Theorem [5, Page 32], and its corresponding version for simple mixed graphs
appears in [11, Theorem 2.6].

###### Theorem 2.1

Let $M$ be a mixed multigraph of order $n$ with the Hermitian characteristic
polynomial $\mathnormal{\Phi}(M,\lambda)=\sum_{i=0}^{n}c_{i}\lambda^{n-i}$.
Then

$c_{i}=\sum_{S}(-1)^{r(S)}\prod_{C\subset S}\nu(C),$

where the sum runs over all Sachs subgraphs $S$ of order $i$ in $M$, and
$r(S)$ is the number of connected components in $S$.

###  2.2 Applications of Theorem 2.1

As an application of Theorem 2.1, we determine which mixed multigraphs can be
antispectral with their underlying graphs. We start this subsection with the
following observation.

###### Observation 2.2

Let $C$ be a mixed cycle, and let $f$ $($$b$, resp.$)$ be the number of
forward $($backward, resp.$)$ arcs in $C$ with arbitrary cycle direction. By
the definition of $\nu(C),$ we have

$\nu(C)=2\Leftrightarrow|f-b|\equiv 0({\rm mod}\ 6)\Leftrightarrow wt(C)=1;$
$\nu(C)=-2\Leftrightarrow|f-b|\equiv 3({\rm mod}\ 6)\Leftrightarrow wt(C)=-1;$
$\nu(C)=1\Leftrightarrow|f-b|\equiv 1({\rm mod}\ 6)~{}or~{}|f-b|\equiv 5({\rm
mod}\ 6)\Leftrightarrow wt(C)=\omega~{}or~{}wt(C)=\omega^{5};$
$\nu(C)=-1\Leftrightarrow|f-b|\equiv 2({\rm mod}\ 6)~{}or~{}|f-b|\equiv 4({\rm
mod}\ 6)\Leftrightarrow wt(C)=\omega^{2}~{}or~{}wt(C)=\omega^{4}.$

###### Theorem 2.3

Let $M$ be a mixed multigraph of order $n$. Then, $M$ is antispectral to its
underlying graph if and only if every even mixed cycle of $M$ has weight $1$
and every odd mixed cycle of $M$ has weight $-1$.

Proof. Write $G=G(M)$. Let
$\mathnormal{\Phi}(G,\lambda)=\sum_{i=0}^{n}c_{i}\lambda^{n-i}$ and
$\mathnormal{\Phi}(M,\lambda)=\sum_{i=0}^{n}c^{\prime}_{i}\lambda^{n-i}$.
Then, $M$ and $G$ are antispectral if and only if $c_{j}=c^{\prime}_{j}$ (for
even $j$) and $c_{j}=-c^{\prime}_{j}$ (for odd $j$).

The sufficiency is easily verified by Theorem 2.1 and Observation 2.2, and we
only prove the necessity. Assume to the contrary. There exists either some
even cycles with weight no equal to $1$ or some odd cycles with weight not
equal to $-1$. Let $k$ be the minimum length among these cycles.

Case 1: $k$ is even. In order to yield a contradiction, we need to calculate
$c_{k}$ and $c^{\prime}_{k}$ using Theorem 2.1. Let $S_{1}$ and
$S_{1}^{\prime}$ be two corresponding Sachs subgraphs of order $k$ consisting
of $k/2$ isolated edges of $G$ and $M$, respectively. Clearly,

$(-1)^{r(S_{1})}\prod_{C\subset
S_{1}}\nu(C)=(-1)^{r(S^{\prime}_{1})}\prod_{C\subset
S^{\prime}_{1}}\nu(C)=(-1)^{k/2}.$

Let $S_{2}$ and $S_{2}^{\prime}$ be two corresponding Sachs subgraphs of order
$k$ containing at least one cycle with length less than $k$ of $G$ and $M$,
respectively. Notice that all even (odd, resp.) mixed cycles of length less
than $k$ in $M$ have weight $1$ ($-1$, resp.) and the fact that every Sachs
subgraph $S_{2}$ (and $S_{2}^{\prime}$) contains even number of odd mixed
cycles. It follows that

$(-1)^{r(S_{2})}\prod_{C\subset
S_{2}}\nu(C)=(-1)^{r(S^{\prime}_{2})}\prod_{C\subset S^{\prime}_{2}}\nu(C).$

Let $S_{3}$ and $S_{3}^{\prime}$ be two corresponding cycles of $G$ and $M$
with length $k$, respectively. By Theorem 2.1, we deduce that

$c_{k}-c^{\prime}_{k}=\sum_{S_{3}}(-1)\times
2-\sum_{S_{3}^{\prime}}(-1)\times\nu(S_{3}^{\prime}).$

Then, the fact $c_{k}=c^{\prime}_{k}$ forces that for any $S_{3}^{\prime}$,
its weight is $1$ by Observation 2.2, a contradiction.

Case 2: $k$ is odd. The proof is similar to Case 1, which is left to the
reader.

###### Remark 2.4

Using the similar proof in Theorem 2.3, we can also obtain that a mixed
multigraph and its underlying graph are cospectral if and only if all mixed
cycles in the mixed multigraph have weight $1$.

The following two consequences immediately follow from Theorem 2.1 since the
value of any cycle is invariant if we change the orientation of a bridge.

###### Corollary 2.5

If $uv$ is a bridge of a mixed multigraph, then the spectrum is invariant when
we change the direction of $uv$.

###### Proposition 2.6

All mixed forests with the same underlying graph are cospectral.

##  3 Cospectral operations on mixed multigraphs

From the perspective of spectral analysis, there are many cospectral mixed
graphs with the same underlying graph. Thus, researchers turn to consider the
cospectral problem on classes of “switching equivalent” mixed graphs rather
than on individual mixed graphs [11, 13, 16, 17]. Motivated by this, in this
section, we will present operations that preserve the spectrum of mixed
multigraphs. For similar cospectral operations on simple mixed graphs, one can
refer to Li and Yu [11]. Firstly, we describe our operations in matrix
language below.

###### Definition 3.1

Let $M^{\prime}$ and $M^{\prime\prime}$ be two mixed multigraphs with the same
underlying graph. A three-way switching is the operation of changing
$M^{\prime}$ into $M^{\prime\prime}$, if there exists a diagonal matrix $D$
with $D_{vv}\in\\{\omega^{i}|0\leq i\leq 5\\}$ such that

$N(M^{\prime\prime})=D^{-1}N(M^{\prime})D,$

or equivalently,

$N_{e^{\prime\prime}_{uv}}=D^{-1}_{uu}N_{e^{\prime}_{uv}}D_{vv}$

for any corresponding edges $e^{\prime}_{uv}$ and $e^{\prime\prime}_{uv}$.

Definition 3.1 implies that if $M^{\prime\prime}$ is obtained from
$M^{\prime}$ by a sequence of three-way switchings, then $M^{\prime\prime}$
can be obtained from $M^{\prime}$ by a single three-way switching, and the
operation of three-way switching is invertible, that is, $M^{\prime}$ can be
also obtained from $M^{\prime\prime}$ by a three-way switching. The following
proposition is also immediately obtained by Definition 3.1.

###### Proposition 3.2

The three-way switching on any mixed multigraph can give a cospectral mixed
multigraph.

Given two mixed multigraphs with the same underlying graph, even they are
cospectral, it is not easy to determine whether one of them can be obtained
from the other by a three-way switching or not. Next, we provide an equivalent
condition to understand the operation from a structural point of view.

Let $M^{\prime}$ and $M^{\prime\prime}$ be two mixed multigraphs with the same
underlying graph. Taking any mixed cycle in $M^{\prime}$, we first assign a
direction for it and we can obtain the corresponding mixed cycle in
$M^{\prime\prime}$ naturally. Hereafter, discussing two mixed multigraphs with
the same underlying graph, we always assume that all corresponding mixed
cycles of them have the same cycle direction.

###### Theorem 3.3

Let $M^{\prime}$ and $M^{\prime\prime}$ be two connected mixed multigraphs
with the same underlying graph $G$ on $n$ vertices. Then one mixed multigraph
can be obtained from the other by a three-way switching if and only if all
corresponding mixed cycles of them have the same weights.

To prove Theorem 3.3, we need the following lemma.

###### Lemma 3.4

Let $M^{\prime}$ and $M^{\prime\prime}$ be two mixed trees with the same
underlying graph. Then one of them can be obtained from the other by a three-
way switching.

Proof. Let $N(M^{\prime})=[N^{\prime}_{uv}]$ and
$N(M^{\prime\prime})=[N^{\prime\prime}_{uv}]$. Now we define a function
$f:V(M^{\prime})\rightarrow\mathfrak{W}=\\{\omega^{i}|0\leq i\leq 5\\}$ by the
following procedure. First, pick an arbitrary vertex $v$ of $M^{\prime}$ and
set $f(v)=1$, then we expand the definition of $f$ through adjacency relation.
For defined vertex $v$ of $M^{\prime}$ and its undefined neighbor $u,$ let
$f^{-1}(u)N^{\prime}_{uv}f(v)=N^{\prime\prime}_{uv}$, i.e.,
$f(u)=f(v)N^{\prime}_{uv}{N^{\prime\prime}_{uv}}^{-1}$. The above process will
terminate as $M^{\prime}$ is a finite graph. Let $D=[D_{vv}]$ be the diagonal
matrix with $D_{vv}=f(v).$ It is easy to see that
$N(M^{\prime\prime})=D^{-1}N(M^{\prime})D$. The result follows from the
definition of three-way switching.

Proof of Theorem 3.3. Denote by $N(M^{\prime})=[N^{\prime}_{uv}]$ and
$N(M^{\prime\prime})=[N^{\prime\prime}_{uv}]$.

Necessity: By Definition 3.1, there exists a diagonal matrix $D=[D_{vv}]$ such
that $N^{\prime\prime}_{e}=D^{-1}_{uu}N^{\prime}_{e}D_{vv}$ for each edge
$e=uv\in E(G)$. Denote a mixed cycle in $M^{\prime}$ by
$C^{\prime}=v_{1}e^{\prime}_{1}v_{2}e^{\prime}_{2}v_{3}\cdots
v_{s}e^{\prime}_{s}v_{1}$ and its corresponding mixed cycle in
$M^{\prime\prime}$ by
$C^{\prime\prime}=v_{1}e^{\prime\prime}_{1}v_{2}e^{\prime\prime}_{2}v_{3}\cdots
v_{s}e^{\prime\prime}_{s}v_{1}$. Then

$\displaystyle wt(C^{\prime\prime})=$ $\displaystyle
N^{\prime\prime}_{e^{\prime\prime}_{1}}N^{\prime\prime}_{e^{\prime\prime}_{2}}\cdots
N^{\prime\prime}_{e^{\prime\prime}_{s}}$ $\displaystyle=$ $\displaystyle
D^{-1}_{v_{1}v_{1}}N^{\prime}_{e^{\prime}_{1}}D_{v_{2}v_{2}}D^{-1}_{v_{2}v_{2}}N^{\prime}_{e^{\prime}_{2}}D_{v_{3}v_{3}}\cdots
D^{-1}_{v_{s}v_{s}}N^{\prime}_{e^{\prime}_{s}}D_{v_{1}v_{1}}$ $\displaystyle=$
$\displaystyle N^{\prime}_{e^{\prime}_{1}}N^{\prime}_{e^{\prime}_{2}}\cdots
N^{\prime}_{e^{\prime}_{s}}=wt(C^{\prime}).$

Now we prove the sufficiency by induction on the dimension of cycle space of
$M^{\prime}$, say $d$. If $d=0$, then $M^{\prime}$ and $M^{\prime\prime}$ are
two mixed trees with the same underlying graph, and the assertion follows from
Lemma 3.4. We may suppose that $d\geq 1$ and the assertion holds for all
connected mixed multigraphs with dimension less than $d$. Let $M^{\prime}$ be
a connected mixed multigraph with dimension $d$. Take a mixed cycle
$C^{\prime}=v_{1}e^{\prime}_{1}v_{2}e^{\prime}_{2}v_{3}\cdots
v_{s}e^{\prime}_{s}v_{1}$ in $M^{\prime}$ and a mixed edge $e^{\prime}_{1}\in
E(C^{\prime})$ and denote the corresponding mixed cycle and mixed edge in
$M^{\prime\prime}$ by $C^{\prime\prime}$ and $e^{\prime\prime}_{1}$,
respectively. By induction hypothesis, there exists a diagonal matrix
$D=[D_{vv}]$ such that

$N^{\prime\prime}_{e^{\prime\prime}_{uv}}=D^{-1}_{uu}N^{\prime}_{e^{\prime}_{uv}}D_{vv}$

for any corresponding edges $e^{\prime}_{uv}$ and $e^{\prime\prime}_{uv}$ of
$M^{\prime}-e^{\prime}_{1}$ and $M^{\prime\prime}-e^{\prime\prime}_{1}$,
respectively. To complete the proof, it suffices to prove
$N^{\prime\prime}_{e^{\prime\prime}_{1}}=D^{-1}_{v_{1}v_{1}}N^{\prime}_{e^{\prime}_{1}}D_{v_{2}v_{2}}$.
It follows from $wt(C^{\prime})=wt(C^{\prime\prime})$ that

$\displaystyle N^{\prime}_{e^{\prime}_{1}}N^{\prime}_{e^{\prime}_{2}}\cdots
N^{\prime}_{e^{\prime}_{s}}=$ $\displaystyle
N^{\prime\prime}_{e^{\prime\prime}_{1}}N^{\prime\prime}_{e^{\prime\prime}_{2}}\cdots
N^{\prime\prime}_{e^{\prime\prime}_{s}}$ $\displaystyle=$ $\displaystyle
N^{\prime\prime}_{e^{\prime\prime}_{1}}D^{-1}_{v_{2}v_{2}}N^{\prime}_{e^{\prime}_{2}}D_{v_{3}v_{3}}\cdots
D^{-1}_{v_{s}v_{s}}N^{\prime}_{e^{\prime}_{s}}D_{v_{1}v_{1}}.$

The result follows. $\blacksquare$

A mixed cycle $C$ is called positive if $wt(C)=1.$ A mixed multigraph is said
to be positive if each its mixed cycle is positive. Theorem 3.3 easily implies
the following corollary.

###### Corollary 3.5

Let $M$ be a mixed multigraph. Then $M$ can be obtained from its underlying
graph by a three-way switching if and only if $M$ is positive.

Now we describe the operation of a three-way switching in the graphic
structural language. The similar interpretation was given by Li and Yu [11]
for simple mixed graphs. Assume that there is a partition of the vertex set of
a mixed multigraph $M$ into six (possibly empty) sets, $V(M)=V_{1}\cup
V_{\omega}\cup V_{\omega^{2}}\cup V_{\omega^{3}}\cup V_{\omega^{4}}\cup
V_{\omega^{5}}$, and it is called admissible if the following conditions hold:

(1) For each $j\in\\{\omega^{i}|0\leq i\leq 5\\},$ there are no arcs of $M$
directed from $V_{j}$ to $V_{\omega j}.$

(2) For each $j\in\\{\omega^{i}|0\leq i\leq 5\\},$ there are neither
undirected nor directed edges of $M$ with one endpoint in $V_{j}$ and the
other endpoint in $V_{\omega^{3}j}.$

(3) For each $j\in\\{\omega^{i}|0\leq i\leq 5\\},$ all edges of $M$ with one
endpoint in $V_{j}$ and the other endpoint in $V_{\omega^{4}j}$ are arcs
directed from $V_{j}$ to $V_{\omega^{4}j}.$

A three-way switching with respect to an admissible partition $V(M)=V_{1}\cup
V_{\omega}\cup V_{\omega^{2}}\cup V_{\omega^{3}}\cup V_{\omega^{4}}\cup
V_{\omega^{5}}$ is the operation of changing $M$ into the mixed multigraph
$M^{\prime}$ by making the following transformations, see Fig. 1.

(-6.3,1)a (-6.3,-.5)b -¿ab $V_{\omega^{2}}$$V_{\omega^{5}}$(-8,2).6cm1
$V_{\omega^{4}}$(-8,7).6cm2$V_{1}$(-4.5,2).6cm3$V_{\omega^{3}}$(-4.5,7).6cm4$V_{\omega}$(-10,4.5).6cmA(-2.5,4.5).6cmB
(-10.3,4.1)A1 (-10.3,4.9)A2 ¡-A2A1 (-10.5,4.1)A3 (-10.5,4.9)A4 A4A3
(-9.6,4.7)A5 (-8.2,6.5)C1 ¡-A5C1 (-9.8,4.9)A6 (-8.4,6.7)C2 A6C2 (-9.8,4.1)A8
(-8.4,2.3)C4 A8C4 (-9.6,4.3)A7 (-8.1,2.4)C3 -¿A7C3 (-2.2,4.1)B1 (-2.2,4.9)B2
¡-B2B1 (-2,4.1)B3 (-2,4.9)B4 B4B3 (-4.33,2.45)D1 (-2.9,4.3)B3 -¿D1B3
(-4.1,2.3)D2 (-2.7,4.1)B4 D2B4 (-4.3,6.5)B5 (-2.9,4.7)B7 -¿B7B5 (-4.1,6.7)B6
(-2.7,4.9)B8 B6B8 (-8.6,1.9)11 (-8.1,1.4)12 1112 (-8.45,2.05)13 (-7.95,1.55)14
¡-1314 (-8,2.4)19 (-8,6.5)29 ¡-1929 (-7.6,1.9)15 (-4.9,1.9)35 1535
(-7.6,2.2)16 (-4.9,2.2)36 ¡-3616 (-7.6,7.1)25 (-4.9,7.1)45 2545 (-7.6,6.8)26
(-4.9,6.8)46 -¿4626 (-8.6,7)21 (-8.1,7.6)22 2122 (-8.45,6.85)23 (-7.95,7.45)24
-¿2324 (-3.9,7)41 (-4.4,7.6)42 4142 (-4.55,7.45)43 (-4.05,6.85)44 -¿4443
(-3.9,1.9)31 (-4.4,1.4)32 3132 (-4.05,2.05)33 (-4.55,1.55)34 ¡-3334
(-4.5,2.5)X (-4.5,6.5)Y -¿XY (-9.5,4.6)F1 (-4.8,6.6)F2 -¿F2F1 (-9.5,4.4)F3
(-3,4.6)F4 (-3,4.4)F5 (-7.7,6.6)F6 -¿F4F6 (-7.7,2.5)F7(-4.8,2.5)F8 -¿F7F5
-¿F3F8 $V_{\omega^{2}}$$V_{\omega^{5}}$(-8,-6.5).6cm110
$V_{\omega^{4}}$(-8,-1.5).6cm210$V_{1}$(-4.5,-6.5).6cm310$V_{\omega^{3}}$(-4.5,-1.5).6cm410$V_{\omega}$(-10,-4).6cmA
(-2.5,-4).6cmB (-10.3,-4.4)A11 (-10.3,-3.6)A21 ¡-A21A11 (-10.5,-4.4)A31
(-10.5,-3.6)A41 A41A31 (-9.6,-3.8)A51 (-8.2,-2)C11 A51C11 (-9.8,-3.6)A61
(-8.4,-1.8)C21 -¿A61C21 (-9.8,-4.4)A81 (-8.4,-6.2)C41 ¡-A81C41 (-9.6,-4.2)A71
(-8.1,-6.1)C31 A71C31 (-2.2,-4.4)B11 (-2.2,-3.6)B21 ¡-B21B11 (-2,-4.4)B31
(-2,-3.6)B41 B41B31 (-4.33,-6.05)D11 (-2.9,-4.2)B31 D11B31 (-4.1,-6.2)D21
(-2.7,-4.4)B41 ¡-D21B41 (-4.3,-2)B51 (-2.9,-3.8)B71 B71B51 (-4.1,-1.8)B61
(-2.7,-3.6)B81 -¿B61B81 (-8.6,-6.6)111 (-8.1,-7.1)121 111121 (-8.45,-6.45)131
(-7.95,-6.95)141 ¡-131141 (-8,-6.1)191 (-8,-2)291 ¡-291191 (-7.6,-6.6)151
(-4.9,-6.6)351 ¡-151351 (-7.6,-6.3)161 (-4.9,-6.3)361 361161 (-7.6,-1.4)251
(-4.9,-1.4)451 -¿251451 (-7.6,-1.7)261 (-4.9,-1.7)461 461261 (-8.6,-1.5)211
(-8.1,-.9)221 211221 (-8.45,-1.65)231 (-7.95,-1.05)241 -¿231241 (-3.9,-1.5)411
(-4.4,-.9)421 411421 (-4.55,-1.05)431 (-4.05,-1.65)441 -¿441431 (-3.9,-6.6)311
(-4.4,-7.1)321 311321 (-4.05,-6.45)331 (-4.55,-6.95)341 ¡-331341 (-4.5,-6)X1
(-4.5,-2)Y1 -¿Y1X1 (-9.5,-3.9)F11 (-4.8,-1.9)F21 -¿F11F21 (-9.5,-4.1)F31
(-3,-3.9)F41 (-3,-4.1)F51 (-7.7,-1.9)F61 -¿F61F41 (-7.7,-6)F71(-4.8,-6)F81
-¿F51F71 -¿F81F31  Fig. 1: Three-way switching with respect to an admissible
partition.

(1) For each $j\in\\{\omega^{i}|0\leq i\leq 5\\},$ replacing each undirected
edge between $V_{j}$ and $V_{\omega j}$ with a single arc directed from
$V_{j}$ to $V_{\omega j}.$

(2) For each $j\in\\{\omega^{i}|0\leq i\leq 5\\},$ replacing each arc directed
from $V_{j}$ to $V_{\omega^{5}j}$ with a single undirected edge.

(3) For each $j\in\\{\omega^{i}|0\leq i\leq 5\\},$ reversing the direction of
all arcs directed from $V_{j}$ to $V_{\omega^{4}j}$.

###### Theorem 3.6

If a partition $V(M)=V_{1}\cup V_{\omega}\cup V_{\omega^{2}}\cup
V_{\omega^{3}}\cup V_{\omega^{4}}\cup V_{\omega^{5}}$ is admissible, then the
mixed multigraph $M^{\prime}$ obtained from $M$ by a three-way switching is
cospectral with $M.$

Proof. Let $D$ be the diagonal matrix such that
$D_{vv}=j\in\\{\omega^{i}|0\leq i\leq 5\\}$ if $v\in V_{j}.$ It is easy to
check that $N(M^{\prime})=D^{-1}N(M)D$. The result follows.

###### Definition 3.7

Let $M$ be a mixed multigraph. The converse of $M$, denoted by $M^{T}$, is the
mixed multigraph obtained by reversing the direction of all arcs of $M$.

By Definition 3.7, we see that a mixed multigraph $M$ and its converse $M^{T}$
are cospectral since $N(M^{T})=N(M)^{T}=\overline{N(M)}.$ This implies the
following result.

###### Proposition 3.8

Let $M$ be a mixed multigraph. If $C^{\prime}$ and $C^{\prime\prime}$ are two
corresponding mixed cycles in $M$ and $M^{T}$, respectively, then
$wt(C^{\prime})=\overline{wt(C^{\prime\prime})}$.

Combining Theorem 3.3 with Proposition 3.8, we observe that the operation of
converse does not belong to three-way switching. Based on this, we present the
following definition.

###### Definition 3.9

Two mixed multigraphs $M^{\prime}$ and $M^{\prime\prime}$ are said to be
switching equivalent if one can be obtained from the other by a three-way
switching and/or taking a converse.

Denote by $\mathscr{M}(G)$ the set of all mixed multigraphs whose underlying
graph is the undirected multigraph $G$. Next, we will show that switching
equivalence forms an equivalence relation on $\mathscr{M}(G)$. We use
$\mathfrak{W}=\\{\omega^{i}|0\leq i\leq 5\\}$ to denote the multiplicative
group generated by $\omega$ and use $\mathfrak{D}$ to denote the set of all
diagonal matrices whose diagonal elements belong to $\mathfrak{W}$. For a
mixed multigraph $M$, each $D\in\mathfrak{D}$ corresponds to a partition
$V(M)=V_{1}\cup V_{\omega}\cup V_{\omega^{2}}\cup V_{\omega^{3}}\cup
V_{\omega^{4}}\cup V_{\omega^{5}}$, where $V_{j}=\\{v\in
V(M)|D_{vv}=j\\},j\in\mathfrak{W}$.

###### Theorem 3.10

Let $G$ be an undirected multigraph. Then switching equivalence forms an
equivalence relation on the set $\mathscr{M}(G).$

Proof. Note that switching equivalent mixed multigraphs have the same
underlying graph. Since $\mathfrak{D}$ is a group for matrix multiplication,
the similarity relation with matrices in $\mathfrak{D}$ is symmetric and
transitive. It is easy to see that $\mathfrak{D}$ is closed for complex
conjugation and that $N^{T}=\overline{N}$. If $M^{\prime\prime}$ is obtained
from $M^{\prime}$ by a similarity transformation following by taking the
converse, then

$N(M^{\prime\prime})=\overline{D^{-1}N(M^{\prime})D}=\overline{D^{-1}}~{}\overline{N(M^{\prime})}~{}\overline{D}=D~{}\overline{N(M^{\prime})}~{}D^{-1}.$

It follows that $M^{\prime\prime}$ is obtained by a three-way switching from
the converse of $M^{\prime}$. This now easily implies the result.

###### Remark 3.11

The above proof implies that the switching equivalence class of a mixed
multigraph contains all mixed multigraphs obtained from itself or from its
converse by a single application of a three-way switching.

Combining Theorem 3.3, Proposition 3.8 with Theorem 3.10, we now provide an
equivalent characterization of switching equivalence between two mixed
multigraphs.

###### Theorem 3.12

Two connected mixed multigraphs with the same underlying graph are switching
equivalent if and only if the weights of all corresponding mixed cycles of
them are equal or conjugate to each other.

##  4 The number of cospectral classes

As an application of Section 3, in the last section we study the number of
cospectral classes in $\mathscr{M}(G)$, denoted by $n_{c}(G)$. It is obvious
that cospectral relation forms an equivalence relation on $\mathscr{M}(G)$.
Since mixed multigraphs in the same switching equivalence class are
cospectral, $n_{c}(G)\leq n_{s}(G),$ where $n_{s}(G)$ denotes the number of
switching equivalence classes in $\mathscr{M}(G)$.

Let $G$ be a connected mixed multigraph and $T$ be a spanning tree of $G$. For
any $e\in E(G)\backslash E(T)$, adding $e$ to $T$, we obtain the resultant
graph containing the unique cycle, called the fundamental cycle of $G$ with
respect to $T$ and $e$, denoted by $C_{T}(e)$. Set $\\{C_{T}(e):e\in
E(G)\backslash E(T)\\}$ is denoted by $\mathbf{B}_{T}(G)$ and is said to be
the fundamental cycle basis of $G$ with respect to $T$.

Using the notation fundamental cycle basis, the following theorem gives a more
brief condition than Theorem 3.12 to characterize the switching equivalence
between two mixed multigraphs.

###### Theorem 4.1

Two connected mixed multigraphs with the same underlying graph are switching
equivalent if and only if the weights of all corresponding fundamental cycles
of them are equal or conjugate to each other.

To prove Theorem 4.1, we need the following lemma.

###### Lemma 4.2

Let $M^{\prime}$ and $M^{\prime\prime}$ be two connected mixed multigraphs on
$n$ vertices with the same underlying graph $G$, and let $T$ be a spanning
tree of $G$. Then one mixed multigraph can be obtained from the other by a
three-way switching if and only if for each fundamental cycle
$C\in\mathbf{B}_{T}(G)$, $wt_{M^{\prime}}(C)=wt_{M^{\prime\prime}}(C)$.

Proof. The necessity follows from Theorem 3.3, and we only prove the
sufficiency. Denote by
$N(M^{\prime})=[N^{\prime}_{uv}],~{}N(M^{\prime\prime})=[N^{\prime\prime}_{uv}]$.
Lemma 3.4 implies that there exists a diagonal matrix $D=[D_{vv}]$ such that
for each edge $e=uv\in E(T)$,
$N^{\prime\prime}_{e}=D^{-1}_{uu}N^{\prime}_{e}D_{vv}$. By Definition 3.1, it
is sufficient to show that for each edge $f=xy\in E(G)\backslash E(T)$,
$N^{\prime\prime}_{f}=D^{-1}_{xx}N^{\prime}_{f}D_{yy}$. Denote by
$C_{T}(f)=v_{1}e_{1}v_{2}\cdots e_{s-1}xfy$, where $x=v_{s},y=v_{1}$. The
condition implies that
$wt_{M^{\prime}}(C_{T}(f))=wt_{M^{\prime\prime}}(C_{T}(f))$, equivalently,

$N^{\prime}_{e_{1}}\cdots
N^{\prime}_{e_{s-1}}N^{\prime}_{f}=N^{\prime\prime}_{e_{1}}\cdots
N^{\prime\prime}_{e_{s-1}}N^{\prime\prime}_{f}.$

For any $i=1,2,\ldots,s-1$, noting that $e_{i}\in E(T)$, we have

$N^{\prime\prime}_{e_{i}}=D^{-1}_{v_{i}v_{i}}N^{\prime}_{e_{i}}D_{v_{i+1}v_{i+1}},$

which yields
$N^{\prime\prime}_{f}=D^{-1}_{v_{s}v_{s}}N^{\prime}_{f}D_{v_{1}v_{1}}$. The
result follows.

Proof of Theorem 4.1. The necessity follows from Theorem 3.12, and we only
prove the sufficiency. If for each fundamental cycle $C\in\mathbf{B}_{T}(G)$,
$wt_{M^{\prime}}(C)=wt_{M^{\prime\prime}}(C)$, then Lemma 4.2 implies that the
conclusion holds. If for each fundamental cycle $C\in\mathbf{B}_{T}(G)$,
$wt_{M^{\prime}}(C)=\overline{wt_{M^{\prime\prime}}(C)}$, then, taking the
converse of $M^{\prime\prime}$, we obtain the resultant graph, denoted by
$(M^{\prime\prime})^{T}.$ By Proposition 3.8, for every fundamental cycle
$C\in\mathbf{B}_{T}(G)$,
$wt_{(M^{\prime\prime})^{T}}(C)=\overline{wt_{M^{\prime\prime}}(C)}=wt_{M^{\prime}}(C).$
The result follows from Remark 3.11 and Lemma 4.2. $\blacksquare$

###### Remark 4.3

Let $M^{\prime}$ and $M^{\prime\prime}$ be two connected mixed multigraphs
with the same underlying graph $G$, and let $T$ be a spanning tree of $G$.
Then Theorems 3.12 and 4.1 imply that,
$wt_{M^{\prime}}(C)=wt_{M^{\prime\prime}}(C)$
$($$wt_{M^{\prime}}(C)=\overline{wt_{M^{\prime\prime}}(C)}$$)$ for each cycle
$C$ in $G$ if and only if $wt_{M^{\prime}}(C)=wt_{M^{\prime\prime}}(C)$
$($$wt_{M^{\prime}}(C)=\overline{wt_{M^{\prime\prime}}(C)}$$)$ for each
fundamental cycle $C\in\mathbf{B}_{T}(G)$.

At the end of this paper, we provide an upper bound of the number of switching
equivalence classes in the set of mixed multigraphs with the same underlying
graph, which is naturally an upper bound of the number of cospectral classes.
Similar results for Hermitian adjacency matrix of the first kind can be
referred to Wang and Yuan [17].

Let $G$ be a connected $k$-cyclic undirected multigraph, and let $T$ be a
spanning tree of $G$. Denote
$\mathbf{B}_{T}(G):=\\{C_{1},C_{2},\cdots,C_{k}\\}$ by the fundamental cycle
basis of $G$. For any $M\in\mathscr{M}(G)$ with the given cycle direction,
define the ordered sequence
$\mathfrak{s}(M)=(wt(C_{1}),wt(C_{2}),\ldots,wt(C_{k}))$ as the essential
vector of $M$ which is dependent of $T$ and the given cycle direction. Let
$M^{\prime}\in\mathscr{M}(G)$ and $M^{\prime\prime}\in\mathscr{M}(G),$ and
recall that we always assume that all corresponding mixed cycles of them have
the same cycle direction. Two vectors $\mathfrak{s}(M^{\prime})$ and
$\mathfrak{s}(M^{\prime\prime})$ are called conjugate equivalent if
$\mathfrak{s}(M^{\prime})=\mathfrak{s}(M^{\prime\prime})$ or
$\mathfrak{s}(M^{\prime})=\overline{\mathfrak{s}(M^{\prime\prime})}.$

Let $\mathcal{S}(G)$ be the set of essential vectors of all mixed multigraphs
in $\mathscr{M}(G)$. It is easy to see that the conjugate equivalence
naturally forms an equivalence relation on $\mathcal{S}(G)$. Further, Theorem
4.1 implies that determining $n_{s}(G)$ is equivalent to determining the value
of conjugate equivalence classes in $\mathcal{S}(G)$. Thus, the following
upper bound of $n_{s}(G)$ can be obtained immediately.

###### Theorem 4.4

For a connected $k$-cyclic $(k\geq 1)$ undirected multigraph $G$,
$n_{c}(G)\leq n_{s}(G)\leq\frac{6^{k}}{2}+2^{k-1}$.

Proof. Denote by $a_{i}$ the number of conjugate equivalence classes in
$\mathcal{S}(G)$ whose essential vectors have exactly $i$ imaginary entries at
the same position. If $i=0$, then the corresponding essential vectors are real
vectors and thus $a_{0}\leq 2^{k}$. If $1\leq i\leq k$,
$a_{i}\leq\frac{1}{2}\binom{k}{i}2^{k+i}$. Then

$n_{s}(G)=\sum_{i=0}^{k}a_{i}\leq
2^{k}+\sum_{i=1}^{k}\frac{1}{2}\binom{k}{i}2^{k+i}=\frac{6^{k}}{2}+2^{k-1}.$

The result follows.

## References

  * [1] S. Akbari, A. Ghafaria, M. Nahvib, M. A. Nematollahia, Mixed paths and cycles determined by their spectrum,  _Linear Algebra Appl._ , 2020, 586: 325-346.
  * [2] C. Chen, J. Huang, S.-C. Li, On the relation between the H-rank of a mixed graph and the matching number of its underlying graph,  _Linear Multilinear Algebra_ , 2018, 66: 1853-1869.
  * [3] C. Chen, S.-C. Li, M.-J. Zhang, Relation between the H-rank of a mixed graph and the rank of its underlying graph,  _Discrete Math._ , 2019, 342: 1300-1309.
  * [4] C. Chun, D. Mayhew, M. Newman, Obstacles to decomposition theorems for sixth-root-of-unity matroids,  _Ann. Comb._ , 2015, 19(1): 79-93.
  * [5] D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs, Third edition,  _Johann Abrosius Barth Heidelberg_ , 1995.
  * [6] G. Greaves, B. Mohar, S. O, Interlacing families and the Hermitian spectral norm of digraphs,  _Linear Algebra Appl._ , 2019, 564: 201-208.
  * [7] K. Guo, B. Mohar, Hermitian adjacency matrix of digraphs and mixed graphs,  _J. Graph Theory_ , 2017, 85(1): 217-248.
  * [8] D. Hu, X.-L. Li, X.-G. Liu, S.-G. Zhang, The spectral distribution of random mixed graphs,  _Linear Algebra Appl._ , 2017, 519: 343-365.
  * [9] M. Kadyan, B. Bhattacharjya, Switching equivalence of Hermitian adjacency matrix of mixed graphs, arXiv:2103.13632.
  * [10] M. Kalmykova, B. Kniehla, “Sixth root of unity” and Feynman diagrams: hypergeometric function approach point of view,  _Nuclear Phys. B Proc. Suppl._ , 2010, 205-206.
  * [11] S.-C. Li, Y.-T. Yu, Hermitian adjacency matrix of the second kind for mixed graphs,  _Discrete Math._ , 2022, 345, 112798.
  * [12] J.-X. Liu, X.-L. Li, Hermitian-adjacency matrices and Hermitian energies of mixed graphs,  _Linear Algebra Appl._ , 2015, 466: 182-207.
  * [13] B. Mohar, Hermitian adjacency spectrum and switching equivalenceof mixed graphs,  _Linear Algebra Appl._ , 2016, 489: 324-340.
  * [14] B. Mohar, A new kind of Hermitian matrices for digraphs,  _Linear Algebra Appl._ , 2020, 584: 343-352.
  * [15] F.-L. Tian, D. Wong, Nullity of Hermitian adjacency matrices of mixed graphs,  _J. Math. Res. Appl._ , 2018, 38: 23-33.
  * [16] Y. Wang, B.-J. Yuan, S.-D. Li, C.-J. Wang, Mixed graphs with H-rank 3,  _Linear Algebra Appl._ , 2017, 524: 22-34.
  * [17] Y. Wang, B.-J. Yuan, On graphs whose orientations are determined by their Hermitian spectra,  _Electronic J. Combin._ , 2020, 27(3): #P3.55.
  * [18] G. Whittle, On matroids representable over GF(3) and other fields. Trans,  _Amer. Math. Soc._ , 1997, 349(2): 579-603.
  * [19] P. Wissing, E. R. van Dam, The negative tetrahedron and the first infinite family of connected digraphs that are strongly determined by the Hermitian spectrum,  _J. Comb. Theory A._ , 2020, 173: 105232.
  * [20] G.-H. Yu, H. Qu, Hermitian Laplacian matrix and positive of mixed graphs,  _Appl. Math. Comput._ , 2015, 269: 70-76.