Let \(G\) be a simple connected mixed graph, and let \(H(G)\) denote the Hermitian adjacency matrix of \(G\). The Hermitian permanental polynomial of \(G\) is defined as \(\pi(G; x) = \operatorname{per}(xI – H(G))\), where \(\operatorname{per}(\cdot)\) represents the permanent and \(I\) is the identity matrix. In this paper, we first derive fundamental properties of the Hermitian permanental polynomial for mixed graphs and establish explicit formulas relating its coefficients to those of the characteristic polynomial. We then analyze the root distribution of this polynomial, determining the number of zero roots for several special classes of mixed graphs. Finally, we characterize mixed graphs that remain cospectral under four‑way switching and prove that this operation preserves the permanental spectrum.
Let \(M\) be an \(n \times n\) matrix with entries \(m_{ij}\) (\(i, j = 1, 2, \dots, n\)). The permanent of \(M\) is defined as \[\begin{aligned} \operatorname{per}(M) = \sum_{\sigma} \prod_{i=1}^{n} m_{i\sigma(i)}, \end{aligned}\] where the sum is over all permutations \(\sigma\) of \(\{1, 2, \dots, n\}\). Valiant [11] has proved that computing the permanent is \(\#P\)-complete, even when restricted to \((0, 1)\)-matrices.
In this paper, unless otherwise specified, we only consider simple graphs without multiple edges or loops. Let \(G_U = (V(G_U), E(G_U))\) be a simple graph with vertex set \(|V(G_U)| =\{v_1,v_2,\ldots,v_n\}\) and edges set \(|E(G_U)| = \{e_1,e_2,\ldots,e_n\}\). A mixed graph is obtained from an undirected graph by orienting a subset of its edges. For a mixed graph \(G\), the underlying graph \(G_U\) of \(G\) is a simple undirected graph. Let \(\varphi\) be an arbitrary orientation of \(G_U\), i.e., assigning a direction to each edge of \(G_U\), and the resulting graph is denoted briefly as \(G^{\varphi}\). Obviously, By definition, both oriented graphs and undirected graphs are special cases of mixed graphs.
Let \(A(G_U) = (a_{ij})_{n \times n}\) be the adjacency matrix of \(G_U\), where \(a_{ij} = 1\) if vertices \(v_i\) and \(v_j\) are adjacent, and \(a_{ij} = 0\) otherwise. Let \(I\) be the identity matrix. The permanental polynomial of the underlying graph \(G_U\) is defined as \[\begin{aligned} \pi(G_U,x) = \operatorname{per}(xI – A(G_U)) = \sum_{j=0}^{n}a_{j}x^{n-j}, \end{aligned}\] where \(a_0 = 1\) and \(a_{j}\) denotes the coefficient of the polynomial \(\pi(G_U,x)\).
For a mixed graph \(G\) with vertex set \(V = V(G)\) and edge set \(E = E(G)\), we consider its Hermitian adjacency matrix \(H = H(G)=(h_{uv})_{n \times n} \in \mathbb{C}^{|V| \times |V|}\), where the entry \(h_{uv}\) is defined as follows: \[\begin{aligned} h_{uv} = \begin{cases} 1 & \text{if } uv \in E \text{ and } vu \in E, \\ i & \text{if } uv \in E \text{ but } vu \notin E, \\ -i & \text{if } uv \notin E \text{ but } vu \in E, \\ 0 & \text{otherwise}, \end{cases} \end{aligned}\] where \(i\) is the imaginary number, i.e., \(i^2=-1\). Liu and Li [5] introduced this matrix and studied its fundamental properties. Independently, Guo and Mohar [3] also adopted the same matrix in their research on digraphs and mixed graphs.
For a mixed graph \(G\) with Hermitian adjacency matrix \(H(G)\), its Hermitian permanental polynomial \(\pi(G, x)\) and characteristic polynomial \(\phi(G, x)\) are defined by \[\begin{aligned} \pi(G, x) &= \operatorname{per}(xI – H(G)) = \sum_{k=0}^{n} b_{k}(G) x^{n-k}, \\ \phi(G, x) &= \det(xI – H(G)) = \sum_{k=0}^{n} c_{k}(G) x^{n-k}, \end{aligned}\] where \(b_0(G) = c_0(G) = 1\), and \(b_k(G)\), \(c_k(G)\) denote the respective coefficients for \(k = 0, 1, \ldots, n\).
The roots of the permanental polynomial are called the permanental roots, and the permanental spectrum refers to the multiset consisting of all roots of the permanental polynomial. Let \(\operatorname{Spec}_{\mathrm{per}}(G)\) denote the Hermitian permanental spectra of \(G\). The multiplicity of the zero root in the permanental polynomial \(\pi(G, x)\) of a mixed graph \(G\) is called the number of zero roots of the permanental polynomial, denoted by \(\eta_{\mathrm{H-per}}(G)\).
In the study of mixed graphs, we adopt the following definitions from [5]. The value of a mixed walk \(W = v_1 v_2 \cdots v_\ell\) is defined as \(h(W) = h_{12}h_{23} \cdots h_{(\ell-1)\ell}\). A mixed walk is called positive if \(h(W)=1\) and negative if \(h(W)=-1\). Note that if a mixed walk or mixed cycle takes the value \(\alpha\) in one direction, its value in the reverse direction becomes \(\overline{\alpha}\). Thus, if a mixed cycle has value \(1\) (resp. \(-1\)) in one direction, it also has value \(1\) (resp. \(-1\)) in the reverse direction; hence we may simply term such a cycle a positive (resp. negative) mixed cycle without specifying the direction. A mixed graph is said to be positive (resp. negative) if every mixed cycle in it is positive (resp. negative). An elementary graph is a mixed graph whose components are either single edges or mixed cycles, where every edge component is defined to be positive. A real spanning elementary subgraph of a mixed graph \(G\) is an elementary subgraph that contains all vertices of \(G\) and in which every mixed cycle is real, i.e., its value satisfies \(h(C) \in \{+1,-1\}\); otherwise, if \(h(C) \in \{+i,-i\}\), the cycle is called non-real.
The Hermitian adjacency matrix of a mixed graph is an important research direction, and extensive studies have been conducted in recent years. This matrix was introduced by Liu and Li [5] in the study of graph energy. Guo and Mohar [3] introduced the eigenvalues, spectral radius, spectrum and related issues of the Hermitian adjacency matrix for digraphs. In [9], Mohar characterized all mixed graphs with H-rank 2. Wang et al. [12] further investigated the H-rank of mixed graphs, determining the H-ranks of mixed graphs with trees, cycles, and complete bipartite graphs as underlying graphs, respectively. For further research on the Hermitian adjacency matrix of mixed graphs, please refer to [5, 10, 8, 14]. However, as a classic graph polynomial, the permanental polynomial has not yet been studied in the context of the Hermitian adjacency matrix of mixed graphs. Therefore, this paper focuses on the permanental polynomial of the Hermitian adjacency matrix of mixed graphs, systematically investigating its fundamental properties such as coefficients and roots, and further exploring isospectrality issues based on this polynomial.
The rest of this paper is organized as follows. Section 2 investigates the coefficients of the Hermitian permanental polynomial for mixed graphs. We derive an elementary subgraph formula and recurrence relations for these coefficients, and establish their connections with the coefficients of the characteristic polynomial. Section 3 analyzes the root distribution of the permanental polynomial, specifically determining the number of zero roots for mixed trees and mixed unicyclic graphs. Section 4 discusses mixed graphs that share the same permanental spectrum. We prove that the permanental spectrum is invariant under the operation of four-way switching. Finally, Section 5 enumerates the Hermitian permanental polynomials for all mixed graphs on at most 6 vertices, and we count the numbers of such mixed graphs for which there is another mixed graph with the same Hermitian permanental polynomial.
In this section, we mainly investigate the coefficients of the Hermitian permanental polynomials of mixed graphs.
Theorem 2.1.Let \(G\) be a mixed graph on \(n\) vertices. The permanent of its Hermitian adjacency matrix is given by \[\operatorname{per}(H(G)) = \sum\limits_{U} (-1)^{\ell(U)} 2^{c(U)},\] where the sum runs over all real spanning elementary subgraphs \(U\) of \(G\), \(\ell(U)\) denotes the number of negative mixed cycles in \(U\), and \(c(U)\) is the number of mixed cycles in \(U\).
Proof. The permanent is \(\operatorname{per}(H(G)) = \sum_{\sigma} h_{1\sigma(1)}h_{2\sigma(2)} \cdots h_{n\sigma(n)}\). A non-zero term corresponds to a permutation \(\sigma\) expressed as disjoint cycles of length at least 2. Consider a cycle \(C\) with value \(\prod\limits_{e \in C} h_e = i^{d(C)} \cdot (-1)^{\ell(C)}\), where \(d(C)\) is the number of directed edges in \(C\). If \(d(C)\) is odd, then \(i^{d(C)} = \pm i\) is purely imaginary. Since \(H(G)\) is Hermitian, we have \(h_{uv} = \overline{h_{vu}}\), and thus \(\prod\limits_k h_{k\sigma^{-1}(k)} = \overline{\prod_k h_{k\sigma(k)}}\). Hence \(\sigma\) and \(\sigma^{-1}\) have complex conjugate values, and imaginary terms cancel in pairs: \(\prod\limits_k h_{k\sigma(k)} + \prod\limits_k h_{k\sigma^{-1}(k)} = 0\) when \(\prod\limits_k h_{k\sigma(k)}\) is purely imaginary.
Only permutations with all cycles having even \(d(C)\) contribute; these correspond to real elementary subgraphs \(U\), where a mixed cycle is called real if its value is \(\pm 1\) (i.e., \(d(C)\) even). Each cycle of length \(2\) corresponds to an edge with value \(h_{uv}h_{vu}=1\). Each cycle of length greater than \(2\) corresponds to a mixed cycle. There are \(2^{c(U)}\) permutations corresponding to \(U\) because each mixed cycle (of length \(\ge 3\)) has two directions; \(2\)-cycles (edges) have a unique orientation.
For a real elementary subgraph \(U\), each mixed cycle has value \((-1)^{\ell(C)}\), where \(\ell(C)\) counts the number of negative edges in \(C\), and \(\ell(U) = \sum \ell(C)\) is the total number of negative mixed cycles in \(U\). Thus \(U\) contributes \((-1)^{\ell(U)}2^{c(U)}\), and summing over all \(U\) gives the formula. ◻
Theorem 2.2. Let \(G\) be a mixed graph with \(n\) vertices, and let \(H(G)\) be the Hermitian adjacency matrix of \(G\). If \[\begin{aligned} \pi(G,x) = \operatorname{per}(xI – H(G)) = \sum\limits_{i=0}^{n} b_i x^{n-i}, \end{aligned}\] then \[\begin{aligned} b_i = (-1)^i \sum\limits_{U} (-1)^{\ell(U)} 2^{c(U)}, \end{aligned}\] where the sum runs over all real elementary subgraphs \(U\) of \(G\) with \(i\) vertices, \(c(U)\) denotes the number of mixed cycles in \(U\), and \(\ell(U)\) denotes the number of negative mixed cycles in \(U\).
Proof. From the definition of the permanental polynomial, the coefficients satisfy \[\begin{aligned} b_i = (-1)^i \sum\limits_{S \subseteq V(G), |S| = i} \operatorname{per}(H(G)[S]), \end{aligned}\] where \(H(G)[S]\) is the principal submatrix indexed by \(S\). Each \(H(G)[S]\) is the Hermitian adjacency matrix of the induced subgraph \(G[S]\). Applying Theorem 2.1 to \(G[S]\) gives \(\operatorname{per}(H(G)[S]) = \sum\limits_{U_S} (-1)^{\ell(U_S)} 2^{c(U_S)}\), where \(U_S\) runs over all real spanning elementary subgraphs of \(G[S]\). Since every real elementary subgraph \(U\) of \(G\) with \(i\) vertices corresponds uniquely to \(S = V(U)\), summing over all \(S\) yields \[\begin{aligned} b_i = (-1)^i \sum\limits_{U} (-1)^{\ell(U)} 2^{c(U)}, \end{aligned}\] where the sum runs over all real elementary subgraphs \(U\) of \(G\) with \(i\) vertices. ◻
Example 2.3. Consider the mixed triangle \(C_3\) shown in Figure 1 and 2.
By Theorem 2.2, the coefficient \(b_3\) of its permanental polynomial is given by \[b_3 = (-1)^3 \sum_{U} (-1)^{\ell(U)} 2^{c(U)},\] where \(U\) runs over real elementary subgraphs on \(3\) vertices. The only such subgraph is \(C_3\) itself.
If \(C_3\) is positive (all edges undirected), then \(\ell(C_3)=0\), \(c(C_3)=1\), so \(b_3 = -2\). If \(C_3\) is negative (two directed edges and one undirected, oriented consistently), then \(\ell(C_3)=1\), so \(b_3 = 2\). Thus \(b_3 = -2\) for a positive triangle and \(b_3 = 2\) for a negative triangle.
When the mixed graph \(G\) is reduced to an undirected graph by removing all edge directions, we have \(\ell(U) = 0\). In this case, the formula in Theorem 2.1 simplifies to, and thus recovers, the classical results of Kasum et al. [4] and Merris et al. [7]. \[\begin{aligned} a_j(G_U) = (-1)^j \sum_{U \in \mathcal{U}_{j}} 2^{c(U)}, \quad 1 \leq j \leq n, \end{aligned}\] where \(\mathcal{U}_{j}\) denotes the set of all \(j\)-vertex elementary subgraphs of \(G\), and \(c(U)\) is the number of cycles in \(U\). This shows that our result generalizes the prior work from undirected to mixed graphs.
We next establish the relationship between the permanental polynomial of a mixed graph and those of its subgraphs, and derive the following results
Theorem 2.4. (1) Let \(v\) be a vertex of a mixed graph \(G\), and let \(C_v(G)\) denote the set of all real cycles in \(G\) that contain \(v\). Then the Hermitian permanental polynomial satisfies: \[\begin{aligned} {\pi(G, x)} &= x {\pi(G – v, x) }+ \sum_{u \in N(v)} {\pi(G – \{u, v\}, x)} + 2 \sum_{C \in C_v(G)} (-1)^{|V(C)| + \ell(C)} {\pi(G – V(C), x)}, \end{aligned}\] where \(N(v)\) denotes the set of vertices adjacent to \(v\), \(\ell(C) = 1\) if \(C\) is a negative mixed cycle, and \(\ell(C) = 0\) if \(C\) is a positive mixed cycle.
(2) Let \(e = (uv)\) be an edge of a mixed graph \(G\), and let \(C_e(G)\) denote the set of all real cycles in \(G\) that contain \(e\). Then \[\begin{aligned} {\pi(G, x)} = {\pi(G – e, x)} + {\pi(G – u – v, x)} + 2 \sum_{C \in C_e(G)} (-1)^{|V(C)| + \ell(C)} {\pi(G – V(C), x)}, \end{aligned}\] where \(\ell(C) = 1\) if \(C\) is a negative mixed cycle in \(G\), and \(\ell(C) = 0\) if \(C\) is a positive mixed cycle.
Proof. The permanental polynomial is given by \(\pi(G,x) = \text{per}(xI – H(G))\), where the permanent of a matrix is defined as \[\begin{aligned} \text{per}(M) = \sum_{\sigma } \prod_{i=1}^n M_{i\sigma(i)}. \end{aligned}\]
Fix a vertex \(v \in V\), and let \(M = xI – H(G)\). The expansion terms of \(\text{per}(M)\) can be decomposed by cycle decompositions containing \(v\) (i.e., the permutation \(\sigma = \tau\pi'\), where \(\tau\) is a subcycle containing \(v\), and \(\pi'\) is the remaining part).
Case 1. \(\tau = v\). In this case, \(\sigma(v) = v\), so the term contains \(M_{vv} = x\), and the remaining factors correspond to the permanent of \(G – v\). The value is \[\begin{aligned} x \cdot \text{per}(xI – H(G – v)) = x {\pi(G – v, x)}. \end{aligned}\]
Case 2. \(\tau = (v, u)\) (\(u \in N(v)\)). Here, \(\sigma(v) = u\) and \(\sigma(u) = v\). For the adjacent vertex \(u\), we have \(M_{vu}M_{uv} = (-h_{vu})(-h_{uv}) = 1\), and the remaining factors correspond to the permanent of \(G – \{v, u\}\). The total value is \[\begin{aligned} \sum_{u \in N(v)} \text{per}(xI – H(G – \{v, u\})) = \sum_{u \in N(v)} {\pi(G – \{u, v\}, x)}. \end{aligned}\]
Case 3. \(\tau\) is a cycle of length \(\geq 3\). Let \(C\) be a cycle containing \(v\) (with \(|V(C)| = k \geq 3\)), corresponding to \(\tau = (v_1 v_2 \cdots v_k)\) where \(v_1 = v\). The value of this cycle to the permanent is \[\begin{aligned} \prod_{j=1}^k M_{v_j v_{j+1}} = \prod_{j=1}^k (-h_{v_j v_{j+1}}) = (-1)^k \prod_{j=1}^k h_{v_j v_{j+1}} = (-1)^k h(C), \end{aligned}\] where \(v_{k+1} = v_1\), and \(h(C)\) denotes the value of cycle \(C\).
For real mixed cycles, if \(C\) is a positive mixed cycle, then \(h(C) = 1\), \(\ell(C) = 0\), and its value is \((-1)^k\); if \(C\) is a negative mixed cycle, then \(h(C) = -1\), \(\ell(C) = 1\), and its value is \((-1)^k \cdot (-1) = (-1)^{k+1}\).
That is, the sign factor is \((-1)^{k + \ell(C)}\). Each cycle has 2 possible orientations, so the remaining factors correspond to the permanent of \(G – V(C)\). The total value is \[\begin{aligned} 2 \sum_{C \in C_v(G)} (-1)^{|V(C)| + \ell(C)} {\pi(G – V(C), x)}. \end{aligned}\] Combining the above cases, we obtain \[\begin{aligned} {\pi(G, x)} = x {\pi(G – v, x)} + \sum_{u \in N(v)} {\pi(G – \{u, v\}, x)} + 2\sum_{C \in C_v(G)} (-1)^{|V(C)| + \ell(C)} {\pi(G – V(C), x)}. \end{aligned}\]
For part (2), fix an edge \(e = uv \in E(G)\), and let \(M = xI – H(G)\). The expansion terms of \(\operatorname{per}(M)\) can be decomposed by the role of the edge \(e\) in the cycle decomposition of \(\sigma\).
Case 1. The edge \(e\) does not appear as a \(2\)-cycle and is not part of any longer cycle in \(\sigma\). This means that \(\sigma(u) \neq v\) and \(\sigma(v) \neq u\), and \(u\) and \(v\) are not connected through the cycle structure involving \(e\). The contribution from such permutations is exactly \(\pi(G – e, x)\), because removing \(e\) does not affect these terms.
Case 2. \(\sigma(u) = v\) and \(\sigma(v) = u\), i.e., \(\sigma\) contains the \(2\)-cycle \((uv)\). Then \(M_{uv}M_{vu} = (-h_{uv})(-h_{vu}) = 1\), and the remaining factors correspond to the permanent of \(G – u – v\). Thus the contribution from this case is \(\pi(G – u – v, x)\).
Case 3. The edge \(e\) belongs to a cycle \(C\) of length \(k \ge 3\) in \(\sigma\), where \(C = (u = v_1, v_2, \ldots, v_k)\) with \(v_k = v\) (or \(v\) appears elsewhere in the cycle). The contribution of this cycle to the permanent is \[\prod_{j=1}^k M_{v_jv_{j+1}} = \prod_{j=1}^k (-h_{v_jv_{j+1}}) = (-1)^k \prod_{j=1}^k h_{v_jv_{j+1}} = (-1)^k h(C),\] where \(v_{k+1} = v_1\), and \(h(C)\) denotes the value of cycle \(C\). For a real mixed cycle, if \(C\) is positive, then \(h(C)=1\) and the sign is \((-1)^k\); if \(C\) is negative, then \(h(C) = -1\) and the sign is \((-1)^{k+1}\). Thus the sign factor is \((-1)^{k + \ell(C)}\), where \(\ell(C)=1\) for negative cycles and \(0\) for positive cycles. Each such cycle has two possible orientations in the permutation, giving a factor of \(2\). The remaining factors correspond to the permanent of \(G – V(C)\). Summing over all real cycles \(C\) that contain \(e\) yields \[2 \sum_{C \in C_e(G)} (-1)^{|V(C)| + \ell(C)} \pi(G – V(C), x).\]
Combining the three cases, we obtain \[\pi(G, x) = \pi(G – e, x) + \pi(G – u – v, x) + 2 \sum_{C \in C_e(G)} (-1)^{|V(C)| + \ell(C)} \pi(G – V(C), x).\] ◻
Corollary 2.5. Let \(T'\) be any mixed graph of a tree \(T\). Then \(\operatorname{per}(xI – H(T')) = \operatorname{per}(xI – H(T))\).
Corollary 2.6. Let \(T\) be a tree of order \(n\), and let \(T'\) be any mixed graph obtained by orienting some edges of \(T\). If \(T'\) has a perfect matching, then \(b_n = \operatorname{per}\bigl(H(T')\bigr) = \operatorname{per}\bigl(H(T)\bigr) = 1\).
Lemma 2.7. ([2]) Let \(G\) be a graph with \(n\) vertices and \(m\) edges, and its degree sequence is \((d_1, d_2, \ldots, d_n)\). Let \(\mathcal{m}(G,k)\) denote the number of \(k\)-matchings of \(G\). Then
1. \(\mathcal{m}(G, 1) = m\).
2. \(\mathcal{m}(G, 2) = \dbinom{m}{2} – \sum\limits_{i=1}^n \dbinom{d_i}{2}\).
3. \(\mathcal{m}(G, 3) = \dbinom{m}{3} – (m – 2) \sum\limits_{i=1}^n \dbinom{d_i}{2} + 2 \sum\limits_{i=1}^n \dbinom{d_i}{3} + \sum\limits_{ij \in E(G)} (d_i – 1)(d_j – 1) – \mathcal{t}\), where \(\mathcal{t}\) is the number of triangles in \(G\).
An elementary graph on 3 vertices is a triangle, while one on 4 vertices consists either of two disjoint edges or a 4-cycle. Applying Theorem 2.2 together with Lemma 2.7 yields the following result.
Lemma 2.8. Let \(G\) be a mixed graph on \(n\) vertices and \(m\) edges, with degree sequence \((d_1,d_2,\ldots,d_n)\). Let its Hermitian permanental polynomial be \(\pi(G,x)=\sum\limits_{j=0}^{n} b_{j}(G)x^{n-j}\). Then the first five coefficients are given by \[\begin{aligned} &b_0(G)=1,\quad b_1(G)=0,\quad b_2(G)=m,\\[2pt] &b_3(G)=2(\mathcal{t}'-\mathcal{t}''),\\[2pt] &b_4(G)=\binom{m}{2}-\sum_{j=1}^{n}\binom{d_j}{2}-2(\mathcal{q}'-\mathcal{q}''), \end{aligned}\] where \(\mathcal{t}'\) and \(\mathcal{t}''\) denote the numbers of negative and positive mixed \(3\)-cycles in \(G\), respectively, and \(\mathcal{q}'\), \(\mathcal{q}''\) denote the numbers of negative and positive mixed \(4\)-cycles in \(G\), respectively.
Proof. By convention, \(b_0=1\). By Theorem 2.2 and Lemma 2.7, we have \[\begin{aligned} b_1 &= 0,\\ b_2 &= (-1)^2 \cdot 2^0 \cdot m = m,\\ b_3 &= (-1)^{3+1} \cdot 2^1 \cdot \mathcal{t}' + (-1)^3 \cdot 2^1 \cdot \mathcal{t}'' = 2(\mathcal{t}'-\mathcal{t}''),\\ b_4 &= \binom{m}{2} – \sum_{j=1}^{n} \binom{d_j}{2} + \bigl[(-1)^{4+1} \cdot 2^1 \cdot \mathcal{q}' + (-1)^4 \cdot 2^1 \cdot \mathcal{q}''\bigr] \\ &= \binom{m}{2} – \sum_{j=1}^{n} \binom{d_j}{2} – 2(\mathcal{q}'-\mathcal{q}''). \end{aligned}\] ◻
The rank and corank of the Hermitian adjacency matrix of a mixed graph \(G\) are defined as: \(r(G) = n – c\), \(s(G) = m – n + c\), where \(n\), \(m\), and \(c\) denote the order, number of edges, and number of connected components of \(G\), respectively. Li et al. [5] gave the coefficient formula of the characteristic polynomial of the Hermitian adjacency matrix of a mixed graph as follows.
Lemma 2.9. [5] Let the coefficients of the characteristic polynomial of a mixed graph \(G\) are given by \[\begin{aligned} (-1)^k c_k = {\sum_{U}} (-1)^{r{(U)} + \ell(U)} 2^{s{(U)}}, \end{aligned}\] where the sum is over all real elementary subgraphs \(U\) of \(G\) with \(k\) vertices, \(r(U)\) denotes the rank of \(U\), \(s(U)\) denotes the corank of \(U\), and \(\ell(U)\) denotes the number of negative mixed cycles in \(U\).
We investigate the relationship between the coefficients of the characteristic polynomial and the Hermitian permanental polynomial of a mixed graph, and present the following result.
Theorem 2.10. Let \(G\) be a mixed graph, and let \(H(G)\) be its Hermitian adjacency matrix. Denote the characteristic polynomial as \(\phi(G,x) = \sum\limits_{k=0}^n (-1)^k c_k x^{n-k}\), and the permanental polynomial as \(\pi(G,x) = \sum\limits_{k=0}^n b_k x^{n-k}\). If one of the following conditions holds
1. \(G\) contains no real mixed cycles; or
2. All real mixed cycles of \(G\) have length \(l \equiv 2 \pmod{4}\) and are negative mixed cycles,
then \(|b_k| = |c_k|\) for all \(k = 0,1,\dots,n\).
Proof. By Theorem 2.2 and Lemma 2.9, we have \[\begin{aligned} b_k = (-1)^k \sum\limits_{U} (-1)^{\ell(U)} 2^{c(U)},\quad {(-1)^k c_k = \sum\limits_{U} (-1)^{r(U) + \ell(U)} 2^{s(U)}}, \end{aligned}\] where \(U\) ranges over all real elementary subgraphs with \(k\) vertices, and \(s(U)\) denotes the corank of \(U\) (which equals the number of cycles in \(U\)).
Thus \(c_k = (-1)^k \sum\limits_{U} (-1)^{r(U) + \ell(U)} 2^{s(U)} = (-1)^k \sum\limits_{U} (-1)^{r(U)} \cdot (-1)^{\ell(U)} 2^{c(U)}\), since \(c(U)=s(U)\). Let \(B = \sum\limits_{U} (-1)^{\ell(U)} 2^{c(U)}\). Then \[\begin{aligned} b_k = (-1)^k B, \quad \text{and} \quad c_k = (-1)^k \sum\limits_{U} (-1)^{r(U)} \cdot (-1)^{\ell(U)} 2^{c(U)}. \end{aligned}\] Thus \(|b_k| = |c_k|\) is equivalent to \(|B| = \left| \sum\limits_{U} (-1)^{r(U)} \cdot (-1)^{\ell(U)} 2^{c(U)} \right|\).
Case 1. \(G\) contains no real mixed cycles. Then \(c(U) = 0\), \(\ell(U) = 0\), and \(U\) is a matching. Let \(U\) have \(\alpha\) edges. Then \(k = 2\alpha\) and \(r(U) = \alpha\). Thus \[\begin{aligned} B = \sum\limits_{U} 1, \quad \sum\limits_{U} (-1)^{r(U)} \cdot (-1)^{\ell(U)} 2^{c(U)} = \sum_{U} (-1)^\alpha. \end{aligned}\]
For a fixed \(k\), \(\alpha\) is fixed, so the two sums differ only by the constant factor \((-1)^\alpha\), and their absolute values are equal.
Case 2. All real mixed cycles of \(G\) have length \(l \equiv 2 \pmod{4}\) and are negative cycles. Let \(U\) have \(\gamma\) cycles and \(\delta\) disjoint edges. Then \(\ell(U) = \gamma\), and \[\begin{aligned} k = \sum_{i=1}^\gamma l_i + 2\delta, \quad r(U) = k – (\gamma + \delta). \end{aligned}\]
Since \(l_i \equiv 2 \pmod{4}\), \(l_i/2\) is an odd number, so \(k/2 \equiv \gamma + \delta \pmod{2}\). Thus \[\begin{aligned} (-1)^{r(U)} = (-1)^{k – (\gamma+\delta)} = (-1)^k \cdot (-1)^{\gamma+\delta} = (-1)^k \cdot (-1)^{k/2}. \end{aligned}\]
For a fixed \(k\), \((-1)^{r(U)}\) is a constant, so \(\sum\limits_{U} (-1)^{r(U)} \cdot (-1)^{\ell(U)} 2^{c(U)} = (-1)^{r(U)} B\), and therefore the absolute values of the two sums are equal.
Combining the above cases, the theorem is proved. ◻
This section investigates the root distribution of the Hermitian permanental polynomial for specific classes of mixed graphs. By analyzing the polynomial’s coefficients, we determine the number of zero roots for mixed trees and mixed unicyclic graphs.
We begin by establishing general symmetry properties of the roots. The following foundational lemma will be used throughout.
Lemma 3.1. [13] Let \(P(x) = x^n + b_1 x^{n-2} + b_2 x^{n-4} + \dots + b_p x^{n-2p}\), where \(p \leq \lfloor n/2 \rfloor\), \(b_i \in \mathbb{R}\), and \(b_p \ne 0\). Then the roots of \(P(x)\) are symmetric with respect to both the real and imaginary axes. Specifically, all non-zero roots occur in real pairs \((a, -a)\) (\(a \in \mathbb{R}\)), purely imaginary pairs \((ib, -ib)\) (\(b \in \mathbb{R}\)), and quadruplets \(\pm a \pm ib\) (\(a, b \in \mathbb{R}\)).
Theorem 3.2. Let \(G\) be a mixed graph of order \(n\) containing no real mixed odd cycles. Then
1. The coefficients of its permanental polynomial satisfy \(b_{2k+1} = 0\) for all \(k = 0,1,2,\ldots\);
2. Its permanental roots are symmetric about the origin in the complex plane.
Proof. Let \(G\) be a mixed graph of order \(n\) with no real mixed odd cycles, and let \(H\) denote its Hermitian adjacency matrix.
(1) By Theorem 2.2, the coefficient \(b_i\) is given by \[b_i = (-1)^i \sum_{U} (-1)^{\ell(U)} 2^{c(U)},\] where the sum runs over all real elementary subgraphs \(U\) of \(G\) with \(i\) vertices. Since \(G\) contains no real mixed odd cycles, every real elementary subgraph \(U\) has an even number of vertices. Therefore, \(b_{2k+1} = 0\) for all \(k \geq 0\). Moreover, each \(b_{2k}\) is a sum of real numbers \((-1)^{\ell(U)} 2^{c(U)}\), so \(b_{2k} \in \mathbb{R}\).
(2) From part (1), the permanental polynomial simplifies to \[\pi(G, x) = x^n + b_2 x^{n-2} + b_4 x^{n-4} + \cdots,\] which can be written as \(\pi(G, x) = x^\sigma p(x^2)\), where \(\sigma = n \bmod 2\) (i.e., \(\sigma = 0\) if \(n\) is even, \(\sigma = 1\) if \(n\) is odd), and \(p\) is a polynomial with real coefficients. For any root \(\lambda\) of \(\pi(G, x)\), we have \(\lambda^\sigma p(\lambda^2) = 0\). If \(\lambda = 0\), then \(-\lambda = 0\) is trivially also a root. If \(\lambda \neq 0\), then \(p(\lambda^2) = 0\), which implies \(p((-\lambda)^2) = p(\lambda^2) = 0\), so \((-\lambda)^\sigma p((-\lambda)^2) = 0\). Hence \(-\lambda\) is also a root. Therefore, the roots are symmetric about the origin, and by Lemma 3.1, they occur in pairs \(\pm a\) (\(a \in \mathbb{R}\)), pairs \(\pm ib\) (\(b \in \mathbb{R}\)), and quadruplets \(\pm a \pm ib\) (\(a,b \in \mathbb{R}\)). ◻
Since mixed bipartite graphs contain no mixed odd cycles, they satisfy the hypothesis of the theorem, yielding an immediate corollary.
Corollary 3.3. Let \(G\) be a mixed bipartite graph. Then
1. \(b_{2k+1} = 0\) for all \(k = 0,1,2,\ldots\);
2. its permanental roots are symmetric about the origin.
Recall that a generalized orientation \(\varphi\) of an undirected graph \(G\) assigns a direction to each edge in a chosen subset \(\mathbb{S} \subseteq E(G)\) [5]. The cases \(\mathbb{S} = E(G)\), \(\mathbb{S} = \emptyset\), and \(\emptyset \subsetneq \mathbb{S} \subsetneq E(G)\) correspond to an oriented graph, an undirected graph, and a mixed graph, respectively. Thus, any mixed graph can be obtained by a generalized orientation of its underlying graph \(G_U\). In an oriented graph, the product of Hermitian edge contributions along any odd cycle is purely imaginary, meaning no real mixed odd cycles exist. This leads to another corollary.
Corollary 3.4. If \(G\) is an oriented graph, then
1. \(b_{2k+1} = 0\) for all \(k = 0,1,2,\ldots\);
2. its permanental roots are symmetric about the origin.
We now determine the number of zero roots, \(\eta_{\mathrm{H-per}}(G)\), for mixed graphs whose underlying graphs are trees or unicyclic graphs. For a mixed unicyclic graph \(G\), let \(C_l\) denote its unique cycle of length \(l\), and let \(G – C_l\) be the subgraph induced by deleting all vertices of \(C_l\). Denote \(p = \nu(G)\) as the size of a maximum matching in \(G\), and \(q = \nu(G – C_l)\).
Theorem 3.5. Let \(T'\) be a mixed tree on \(n\) vertices. Then the number of zero roots of its Hermitian permanental polynomial is \[\eta_{\mathrm{H\!- \!per}}(T') = n – 2\nu(T'),\] where \(\nu(T')\) is the size of a maximum matching in \(T'\).
Proof. Since \(T'\) is a tree, its real elementary subgraphs are precisely matchings. By Theorem 2.2, \[b_i = (-1)^i \sum_{U} (-1)^{\ell(U)} 2^{c(U)},\] where \(U\) runs over all real elementary subgraphs with \(i\) vertices. For a tree, \(i\) must be even. When \(i = 2k\), we have \(b_{2k} = (-1)^{2k} \cdot \mathcal{m}(T',k) = \mathcal{m}(T',k)\), where \(\mathcal{m}(T',k)\) counts the \(k\)-matchings. Let \(p = \nu(T')\). Then \(b_{2p} = \mathcal{m}(T',p) \neq 0\), and \(b_{2k} = 0\) for all \(k > p\). Therefore, \(\eta_{\mathrm{H\!- \!per}}(T') = n – 2p = n – 2\nu(T')\). ◻
Example 3.6. Consider the mixed tree \(T\) shown in Figure 3.
Consider a mixed tree \(T\) on \(4\) vertices as shown in Figure 3, where \(v_1v_2\) is undirected, \(v_2\to v_3\) is directed, and \(v_3v_4\) is undirected. Its matching number is \(\nu(T)=2\). By Theorem 3.5, \(\eta_{H-per}(T)=n-2\nu(T)=4-4=0\). Indeed, the permanental polynomial is \(\pi(T,x)=x^4+3x^2+1\), whose roots are all non-zero, confirming \(\eta=0\).
Theorem 3.7. Let \(G\) be a connected mixed unicyclic graph with \(n\) vertices and a unique odd cycle \(C_l\) (\(l \ge 3\)). Let \(p = \nu(G)\), \(q = \nu(G – C_l)\), and \(\mathcal{d}\) be the total number of directed edges in \(C_l\). Then \[\eta_{\mathrm{H\!- \!per}}(G) = \begin{cases} n – 2p – 1, & \text{if } \mathcal{d} \text{ is even and } p = \frac{l-1}{2} + q, \\ n – 2p, & \text{otherwise}. \end{cases}\]
Proof. Fix a cyclic orientation of \(C_l\). Let \(\mathcal{d}_+\) and \(\mathcal{d}_-\) be the numbers of directed edges in \(C_l\) aligned with and against this orientation, respectively, so \(\mathcal{d} = \mathcal{d}_+ + \mathcal{d}_-\). The Hermitian value of the cycle is \[h(C_l) = i^{\mathcal{d}_+} (-i)^{\mathcal{d}_-} = (-1)^{\mathcal{d}_-} i^{\mathcal{d}}.\]
If \(\mathcal{d}\) is even, then \(i^{\mathcal{d}} = \pm 1\), so \(h(C_l) \in \{\pm1\}\) and \(C_l\) is a real mixed cycle.
If \(\mathcal{d}\) is odd, then \(i^{\mathcal{d}} = \pm i\), so \(h(C_l) \notin \mathbb{R}\) and \(C_l\) is not a real mixed cycle.
Case 1: \(\mathcal{d}\) even. \(C_l\) is real and can be part of a real elementary subgraph.
1. If \(p = \frac{l-1}{2} + q\), then \(l + 2q = 2p + 1\). For any \(q\)-matching \(M\) of \(G – C_l\), the subgraph \(U = C_l \cup M\) is a real elementary subgraph with \(2p+1\) vertices, \(c(U)=1\), and \(\ell(U) = \ell(C_l)\). By Theorem 2.2, each such \(U\) contributes \((-1)^{2p+1} (-1)^{\ell(C_l)} 2 = -(-1)^{\ell(C_l)} 2\) to \(b_{2p+1}\). There are \(m(G – C_l, q)\) such subgraphs, so \[b_{2p+1} = (-1)^{2p+1} \cdot 2 \cdot (-1)^{\ell(C_l)} \cdot m(G – C_l, q) \neq 0.\] Thus, \(\eta_{\mathrm{H\!- \!per}}(G) = n – (2p+1) = n – 2p – 1\).
2. If \(p > \frac{l-1}{2} + q\), then \(2p+1 > l+2q\), and no real elementary subgraph with \(2p+1\) vertices contains \(C_l\), so \(b_{2p+1}=0\). Since \(b_{2p} \neq 0\), we have \(\eta_{\mathrm{H\!- \!per}}(G) = n – 2p\).
Case 2: \(\mathcal{d}\) odd. \(C_l\) is not real, so all real elementary subgraphs are matchings. The largest such subgraph has \(2p\) vertices, giving \(b_{2p} \neq 0\) and \(b_{2p+1}=0\). Hence, \(\eta_{\mathrm{H\!- \!per}}(G) = n – 2p\). ◻
Theorem 3.8. Let \(G\) be a mixed unicyclic graph with \(n\) vertices and a unique even cycle \(C_l\) (\(l \ge 4\) even). Let \(p = \nu(G)\), \(q = \nu(G – C_l)\), and \(\mathcal{d}\) be the total number of directed edges in \(C_l\). Let \(\varepsilon(C_l) = 1\) if \(C_l\) is a negative mixed cycle, and \(\varepsilon(C_l) = 0\) otherwise. Let \(E_1\) be the set of edges between \(C_l\) and \(G – C_l\), and \(\mathcal{M}\) be the set of all \(p\)-matchings of \(G\). Then \[\eta_{\mathrm{H\!- \!per}}(G) = \begin{cases} n – 2p + 2, & \text{if } \mathcal{d} \text{ is even, } p = \dfrac{l}{2} + q, \ l \equiv 0 \pmod{4}, {\ \varepsilon(C_l) = 1,} \\ & \text{and } E_1 \cap M = \emptyset \text{ for all } M \in \mathcal{M}; \\ n – 2p, & \text{otherwise}. \end{cases}\]
Proof. By Theorem 2.2, \(b_i = (-1)^i \sum\limits_{U} (-1)^{\ell(U)} 2^{c(U)}\), where \(U\) ranges over elementary subgraphs with \(i\) vertices. Let \(\varepsilon = \varepsilon(C_l) \in \{0,1\}\) indicate whether \(C_l\) is negative, so \((-1)^{\ell(C_l)} = -1\) when \(\varepsilon = 1\) and \(= 1\) when \(\varepsilon = 0\). The value of \(C_l\) is \(h(C_l) = (-1)^{\ell(C_l)} i^{\mathcal{d}}\).
If \(\mathcal{d}\) is odd, \(h(C_l) \notin \mathbb{R}\), so \(C_l\) is not an elementary subgraph. All elementary subgraphs are matchings, giving \(b_{2p} = \mathcal{m}(G, p) \neq 0\). Thus, \(\eta_{\mathrm{H\!- \!per}}(G) = n – 2p\).
If \(\mathcal{d}\) is even, \(h(C_l) \in \mathbb{R}\), so \(C_l\) is an elementary subgraph.
If \(p \neq l/2 + q\), elementary subgraphs containing \(C_l\) have \(l+2q \neq 2p\) vertices and do not affect \(b_{2p}\). Hence, \(b_{2p} = \mathcal{m}(G, p) \neq 0\) and \(\eta_{\mathrm{H\!- \!per}}(G) = n – 2p\).
If \(p = l/2 + q\), subgraphs consisting of \(C_l\) plus a \(q\)-matching \(M\) from \(G-C_l\) contribute to \(b_{2p}\). Each such subgraph \(U = C_l \cup M\) contributes \(2 \cdot (-1)^{\ell(C_l)}\) (the factor \(2\) accounts for the two orientations of \(C_l\)). Let \(\mathcal{M}_q\) be the set of \(q\)-matchings of \(G – C_l\). Then the total contribution from these subgraphs is \(2(-1)^{\ell(C_l)} \cdot |\mathcal{M}_q| = 2(-1)^{\ell(C_l)} \cdot m(G – C_l, q)\). Therefore \[b_{2p} = \mathcal{m}(G, p) + 2(-1)^{\ell(C_l)} \cdot m(G – C_l, q).\]
If \(l \equiv 2 \pmod{4}\), then \((-1)^{l/2} = -1\) and \(p, q\) have opposite parity. It follows that \(b_{2p} \neq 0\), so \(\eta_{\mathrm{H\!- \!per}}(G) = n – 2p\).
If \(l \equiv 0 \pmod{4}\), consider the structure of maximum matchings. If some \(M \in \mathcal{M}\) intersects \(E_1\), then \(\mathcal{m}(G, p) > 2\mathcal{m}(G-C_l, q)\), ensuring \(|b_{2p}| > 0\) and \(\eta_{\mathrm{H\!- \!per}}(G) = n – 2p\). If \(E_1 \cap M = \emptyset\) for all \(M \in \mathcal{M}\), then every \(p\)-matching is a perfect matching of \(C_l\) plus a \(q\)-matching of \(G-C_l\), implying \(\mathcal{m}(G, p) = 2\mathcal{m}(G-C_l, q)\). In this case, if \(\varepsilon(C_l) = 1\) (i.e., \(C_l\) is negative), then \((-1)^{\ell(C_l)} = -1\), so \[b_{2p} = 2\mathcal{m}(G-C_l, q) + 2(-1) \mathcal{m}(G-C_l, q) = 0.\] Since \(b_{2p-2} \neq 0\), we have \(\eta_{\mathrm{H\!- \!per}}(G) = n – 2p + 2\). If \(\varepsilon(C_l) = 0\), then \(b_{2p} = 4\mathcal{m}(G-C_l, q) \neq 0\), so \(\eta_{\mathrm{H\!- \!per}}(G) = n – 2p\).
This completes the proof. ◻
Example 3.9. Consider the mixed unicyclic graphs shown in Figures 4 and 5.
Non-exceptional case: The graph consists of a positive \(3\)-cycle (all edges undirected) with a pendant path of length \(2\) attached to \(v_1\). Here \(n=5\), \(\nu(G)=2\), \(q=1\), \(l=3\), \(d=0\). Since \(p=2\) and \(\frac{l-1}{2}+q=2\), by Theorem 3.7, \(\eta_{H-per}(G)=n-2p-1=0\).
Exceptional case: The graph consists of a \(4\)-cycle with \(v_1\to v_2\), \(v_2\to v_3\), and \(v_3v_4\), \(v_4v_1\) undirected, so \(h(C_4)=-1\) (negative). Attach pendant vertices \(v_5\) to \(v_1\) and \(v_6\) to \(v_3\). Then \(n=6\), \(\nu(G')=3\), \(q=1\), \(l=4\), \(d=2\), \(l\equiv0\pmod{4}\), and \(C_4\) is negative. By Theorem 3.8, \(\eta_{H-per}(G')=n-2p+2=2\).
In this section, we mainly prove the case where two mixed graphs have the same spectrum. Guo and Mohar [3] proved that the characteristic polynomial of a mixed graph remains spectrally invariant under four-way switching. In this section, we show that the permanental polynomial of a mixed graph has the same property under four-way switching.
The following gives a result for mixed graphs without even cycles, and its proof is similar to that of Theorem 4.2 in [1].
Theorem 4.1. Let \(G\) be an undirected graph. Then \(G\) contains no even cycles if and only if for any two generalized orientations \(\varphi_1\) and \(\varphi_2\) of \(G\) that contain no real mixed odd cycles, \(\operatorname{Spec}_{\mathrm{per}}(G^{\varphi_1}) =\operatorname{Spec}_{\mathrm{per}}(G^{\varphi_2})\).
Proof. (Necessity) If \(G\) contains no even cycles, and \(\varphi_1, \varphi_2\) are any two generalized orientations of \(G\) without real mixed odd cycles, then in \(G^{\varphi_j}\) (\(j=1,2\)).
Since \(G\) has no even cycles, each real elementary subgraph \(U\) in \(G^{\varphi_j}\) can only consist of edges (i.e., matchings). Thus, for any odd number \(2k+1\), \(b_{2k+1}(G^{\varphi_1}) = b_{2k+1}(G^{\varphi_2}) = 0\).
For any even number \(2k\), by Theorem 2.2, we have \[b_{2k}(G^{\varphi_j}) = \sum_{U} (-1)^{2k+\ell(U)} 2^{c(U)} = \sum_{U} 1,\] where the sum ranges over all \(k\)-matchings \(U\) (in this case, \(c(U)=0\) and \(\ell(U)=0\)).
Since the number of \(k\)-matchings \(\mathcal{m}_k(G)\) is independent of the orientation, \(b_{2k}(G^{\varphi_1}) = b_{2k}(G^{\varphi_2}) = \mathcal{m}_k(G)\). Therefore, \(\pi(G^{\varphi_1}; x) = \pi(G^{\varphi_2}; x)\), which implies \(\operatorname{Spec}_{\mathrm{per}}(G^{\varphi_1}) = \operatorname{Spec}_{\mathrm{per}}(G^{\varphi_2})\).
(Sufficiency) We use proof by contradiction. Suppose \(G\) contains an even cycle, but for any two generalized orientations \(\varphi_1\) and \(\varphi_2\) of \(G\) without real mixed odd cycles, \(\operatorname{Spec}_{\mathrm{per}}(G^{\varphi_1}) = \operatorname{Spec}_{\mathrm{per}}(G^{\varphi_2})\). Let \(C\) be the shortest even cycle in \(G\) with length \(2\ell\). For an orientation \(\varphi\), the coefficients of the permanental polynomial of the Hermitian adjacency matrix are
When \(k < 2\ell\), \(b_k = \mathcal{m}_k(G^{\varphi})\).
When \(k = 2\ell\), by Theorem 2.2, we have \[b_{2\ell} = \sum_{U} (-1)^{2\ell + \ell(U)} 2^{c(U)},\] where \(U\) runs over all real elementary subgraphs of \(G^{\varphi}\) with \(2\ell\) vertices. These subgraphs consist of either:
a \(\ell\)-matching (no cycles): contributes \(1\);
a single mixed cycle \(C'\) of length \(2\ell\) (plus possibly additional matching edges, but since \(C\) is the shortest even cycle, no other cycles can appear): each such cycle contributes \(2 \cdot (-1)^{\ell(C')}\) (factor \(2\) for two orientations, \((-1)^{\ell(C')}\) for sign).
Thus, \[b_{2\ell} = \mathcal{m}(G, \ell) + 2 \sum_{C'} (-1)^{\ell(C')},\] where the sum runs over all mixed cycles of length \(2\ell\) in \(G^{\varphi}\), and \(\ell(C') = 1\) if \(C'\) is negative, \(0\) if positive.
Let \(e \in C\), and define
\(n_+(e)\): the number of mixed cycles of length \(2\ell\) containing \(e\) with value \(+1\).
\(n_-(e)\): the number of mixed cycles of length \(2\ell\) containing \(e\) with value \(-1\).
If there exists an edge \(e\) such that \(n_+(e) \neq n_-(e)\), reverse the direction of \(e\) to obtain a new orientation \(\varphi'\). The contribution of matchings remains unchanged: \(\mathcal{m}(G, \ell)\) is invariant, the contribution of cycles not containing \(e\) remains unchanged, and the contribution of cycles containing \(e\) changes by \(-2(n_+(e) – n_-(e))\). Thus, \(b_{2\ell}\) will change, leading to \(\operatorname{Spec}_{\mathrm{per}}(G^{\varphi}) \neq \operatorname{Spec}_{\mathrm{per}}(G^{\varphi'})\), which is a contradiction.
Now suppose that \(n_+(e) = n_-(e)\) for all edges \(e\). We claim that for any \(t\) edges \(e_1, \dots, e_t \in E(G)\), \(n_+(e_1, \dots, e_t) = n_-(e_1, \dots, e_t)\) (i.e., the number of mixed cycles of length \(2\ell\) containing these edges and having value \(\pm 1\) is equal).
We use mathematical induction.
For \(t=1\), the claim follows from \(n_+(e) = n_-(e)\) for all edges \(e\).
Assume the claim holds for \(t\). Consider \(t+1\) edges \(e_1, \dots, e_t, e_{t+1}\). By definition, \[\begin{aligned} n_+(e_1, \dots, e_t) &= n_+(e_1, \dots, e_t, e_{t+1}) + n_+(e_1, \dots, e_t, \bar{e}_{t+1}), \\ n_-(e_1, \dots, e_t) &= n_-(e_1, \dots, e_t, e_{t+1}) + n_-(e_1, \dots, e_t, \bar{e}_{t+1}), \end{aligned}\] where \(n_+(e_1, \dots, e_t, \bar{e}_{t+1})\) (resp. \(n_-(e_1, \dots, e_t, \bar{e}_{t+1})\)) denotes the number of mixed cycles of length \(2\ell\) with value \(+1\) (resp. \(-1\)) containing edges \(e_1, \dots, e_t\), but not \(e_{t+1}\).
By the induction hypothesis, \(n_+(e_1, \dots, e_t) = n_-(e_1, \dots, e_t)\), so \[n_+(e_1, \dots, e_t, e_{t+1}) + n_+(e_1, \dots, e_t, \bar{e}_{t+1}) = n_-(e_1, \dots, e_t, e_{t+1}) + n_-(e_1, \dots, e_t, \bar{e}_{t+1}). \label{new2} \tag{1}\]
Consider the orientation \(\varphi'\) obtained from \(\varphi\) by reversing the orientation of \(e_{t+1}\). Let \(n'_+(e_1, \dots, e_t)\) and \(n'_-(e_1, \dots, e_t)\) denote the numbers of mixed cycles of length \(2\ell\) containing edges \(e_1, \dots, e_t\) with value \(+1\) and \(-1\) respectively, under the orientation \(\varphi'\).
Since reversing \(e_{t+1}\) changes the sign of cycles containing \(e_{t+1}\), we have \[\begin{aligned} n'_+(e_1, \dots, e_t) &= n_-(e_1, \dots, e_t, e_{t+1}) + n_+(e_1, \dots, e_t, \bar{e}_{t+1}) ,\\ n'_-(e_1, \dots, e_t) &= n_+(e_1, \dots, e_t, e_{t+1}) + n_-(e_1, \dots, e_t, \bar{e}_{t+1}). \end{aligned}\]
Applying the assumption to orientation \(\varphi'\) gives \(n'_+(e_1, \dots, e_t) = n'_-(e_1, \dots, e_t)\), hence \[n_-(e_1, \dots, e_t, e_{t+1}) + n_+(e_1, \dots, e_t, \bar{e}_{t+1}) = n_+(e_1, \dots, e_t, e_{t+1}) + n_-(e_1, \dots, e_t, \bar{e}_{t+1}). \label{new3} \tag{2}\]
Subtract Eq. (2) from Eq. (1) \[\begin{aligned} &[n_+(e_1, \dots, e_t, e_{t+1}) + n_+(e_1, \dots, e_t, \bar{e}_{t+1})] – [n_-(e_1, \dots, e_t, e_{t+1}) + n_+(e_1, \dots, e_t, \bar{e}_{t+1})] \\ &= [n_-(e_1, \dots, e_t, e_{t+1}) + n_-(e_1, \dots, e_t, \bar{e}_{t+1})] – [n_+(e_1, \dots, e_t, e_{t+1}) + n_-(e_1, \dots, e_t, \bar{e}_{t+1})]. \end{aligned}\]
Simplifying: \[n_+(e_1, \dots, e_t, e_{t+1}) – n_-(e_1, \dots, e_t, e_{t+1}) = n_-(e_1, \dots, e_t, e_{t+1}) – n_+(e_1, \dots, e_t, e_{t+1}).\]
Thus: \[2[n_+(e_1, \dots, e_t, e_{t+1}) – n_-(e_1, \dots, e_t, e_{t+1})] = 0.\]
Hence \(n_+(e_1, \dots, e_t, e_{t+1}) = n_-(e_1, \dots, e_t, e_{t+1})\), completing the induction.
In particular, take \(t = 2\ell\) (i.e., all edges of the cycle \(C\)), then \(n_+(C) = n_-(C)\). However, under any orientation, a specific even cycle \(C\) is either a positive cycle (\(n_+(C)=1, n_-(C)=0\)) or a negative cycle (\(n_+(C)=0, n_-(C)=1\)), which is a contradiction.
Therefore, the assumption is false, and \(G\) must contain no even cycles. ◻
For a mixed graph \(G\) containing cut edges, since cut edges are not contained in any mixed cycles, we obtain the following conclusion: when changing the orientation of any cut edge (e.g., reversing the direction of a directed cut edge, removing its orientation, or adding an orientation to an undirected cut edge), the permanental spectrum of \(G\) remains unchanged.
Corollary 4.2. Let \(G\) be an undirected graph with cut edges, and let \(\varphi_1\) and \(\varphi_2\) be two generalized orientations of \(G\). If \(\varphi_1\) and \(\varphi_2\) differ only in the orientations of some cut edges, then the permanental spectra of the Hermitian adjacency matrices of \(G^{\varphi_1}\) and \(G^{\varphi_2}\) are the same, i.e., \[\begin{aligned} {\operatorname{Spec}_{\mathrm{per}}(G^{\varphi_1}) = \operatorname{Spec}_{\mathrm{per}}(G^{\varphi_2})}. \end{aligned}\]
Thus, for a mixed graph \(G_1\) containing cut edges, we can change the orientation (or assignment) of some cut edges to obtain a mixed graph \(G_2\) that is not isomorphic to \(G_1\), but still satisfies \(\operatorname{Spec}_{\mathrm{per}}(G_1) = \operatorname{Spec}_{\mathrm{per}}(G_2)\).
By Theorem 2.2, real mixed cycles play an important role in determining the coefficients of the permanental polynomial of a mixed graph. If a mixed graph contains no real mixed cycles, then the coefficients of its permanental polynomial are determined solely by its matchings.
Corollary 4.3. Let \(G\) be a mixed graph containing no real mixed cycles. Then \(b_i = 0\) when \(i\) is odd; and \((-1)^k b_{2k}\) is equal to the number of ways to choose \(k\) disjoint edges in \(G\).
Since mixed forests contain no real mixed cycles, we have:
Corollary 4.4. Let \(F'\) be a mixed forest. Then \(b_i = 0\) when \(i\) is odd; and \((-1)^k b_{2k}\) is equal to the number of ways to choose \(k\) disjoint edges in \(F'\).
Since every elementary subgraph of a mixed forest is a union of disjoint edges, and the values of corresponding principal minors of the same order are equal, we have
Corollary 4.5. For any undirected forest \(F\) and its non-trivial generalized orientation \(\varphi\), it always holds that \(\operatorname{Spec}_{\mathrm{per}}(F) = \operatorname{Spec}_{\mathrm{per}}(F^\varphi)\).
Thus, for any pair of non-isomorphic mixed forests \(F'\) and \(F''\) with the same underlying graph, \(\operatorname{Spec}_{\mathrm{per}}(F') = \operatorname{Spec}_{\mathrm{per}}(F'')\) always holds. From this, we obtain the following conclusion.
Corollary 4.6. For any mixed forest \(F'\) with \(n\) (\(n \geq 2\)) vertices, there always exists a non-isomorphic mixed forest \(F''\) such that \(\operatorname{Spec}_{\mathrm{per}}(F') = \operatorname{Spec}_{\mathrm{per}}(F'')\).
Note that every edge of a forest is a cut edge, so Corollary 4.6 can be regarded as a direct consequence of Corollary 4.2.
The transpose of a mixed graph \(G\) is a mixed graph \(G^T\) with the same vertex set, the same undirected edge set, and arc set \(E_1(G^T) = \{xy \mid yx \in E_1(G)\}\). By the definition of the Hermitian adjacency matrix, if \(G\) is a mixed graph and \(G^T\) is its transpose, then \(H(G^T) = H(G)^T = \overline{H(G)}^T\).
Proposition 4.7. A mixed graph \(G\) and its transpose \(G^T\) have the same Hermitian permanental polynomial.
Proof. Let \(H(G)\) be the Hermitian adjacency matrix of \(G\). By definition, the Hermitian adjacency matrix of the transpose \(G^T\) satisfies \(H(G^T) = H(G)^T\), since transposing the graph reverses the direction of each arc, which corresponds to taking the conjugate transpose of the matrix.
Then the Hermitian permanental polynomial of \(G^T\) is \[\pi(G^T, x) = \operatorname{per}(xI – H(G^T)) = \operatorname{per}(xI – H(G)^T).\]
Since the permanent of a matrix equals the permanent of its transpose, we have \[\operatorname{per}(xI – H(G)^T) = \operatorname{per}((xI – H(G))^T) = \operatorname{per}(xI – H(G)) = \pi(G, x).\]
Therefore, \(\pi(G^T, x) = \pi(G, x)\), i.e., \(G\) and \(G^T\) have the same Hermitian permanental polynomial. ◻
Guo and Mohar [3] revealed a more complex transformation that preserves the \(H\)-spectrum. Suppose the vertex set of \(G\) is partitioned into four (possibly empty) subsets: \(V(G) = V_1 \cup V_{-1} \cup V_i \cup V_{-i}\). An edge \(xy \in E(G)\) is called an edge of type \((j,k)\) if \(x \in V_j\) and \(y \in V_k\) (where \(j,k \in \{\pm 1, \pm i\}\)). The partition is called an admissible partition if it satisfies the following conditions:
(a) There are no digons of type \((1,-1)\) or \((i,-i)\);
(b) All edges of type \((1,i)\), \((i,-1)\), \((-1,-i)\), \((-i,1)\) are contained in digons (see Figure 1).
A four-way switching refers to the operation of transforming the mixed graph \(G\) into a mixed graph \(G'\) with respect to the partition \(V(G) = V_1 \cup V_{-1} \cup V_i \cup V_{-i}\), with the following specific steps (Figure 6):
(c) Reverse the direction of all arcs of type \((1,-1)\), \((-1,1)\), \((i,-i)\), \((-i,i)\);
(d) Replace each digon of type \((1,i)\) with a single arc from \(V_1\) to \(V_i\), and each digon of type \((-1,-i)\) with a single arc from \(V_{-1}\) to \(V_{-i}\);
(e) Replace each digon of type \((1,-i)\) with a single arc from \(V_{-i}\) to \(V_1\), and each digon of type \((-1,i)\) with a single arc from \(V_i\) to \(V_{-1}\);
(f) Replace each non-digon of type \((1,-i)\), \((-1,i)\), \((i,1)\), or \((-i,-1)\) with a digon.
Theorem 4.8. Let \(G\) be a mixed graph, \(V(G) = V_1 \cup V_{-1} \cup V_i \cup V_{-i}\) be an admissible partition, and \(G'\) be the mixed graph obtained from \(G\) by four-way switching. Then \(G'\) and \(G\) have the same Hermitian permanental polynomial.
Proof. Define a diagonal matrix \(D = \operatorname{diag}(d_1, \dots, d_n)\), where \[d_v = \begin{cases} 1, & v \in V_1, \\ -1, & v \in V_{-1}, \\ i, & v \in V_i, \\ -i, & v \in V_{-i}. \end{cases}\]
We first verify entrywise that \(H(G') = D^{-1} H(G) D\). For any two vertices \(u, v \in V(G)\), the entry \((H(G'))_{uv}\) is determined by the orientation and sign of the edge \(uv\) in \(G'\), while \([D^{-1} H(G) D]_{uv} = d_u^{-1} (H(G))_{uv} d_v\). The four-way switching rules and the values of \(d_u\) are chosen so that for each type of edge in the admissible partition, the transformation matches exactly. The verification is summarized in the following table:
\[\begin{array}{|c|c|c|c|c|} \hline u \in & v \in & (H(G))_{uv} & d_u^{-1} d_v & (H(G'))_{uv} \\ \hline V_1 & V_1 & h_{uv} & 1 & h_{uv} \\\hline V_1 & V_{-1} & h_{uv} & -1 & -h_{uv} \\\hline V_1 & V_i & h_{uv} & -i & -i h_{uv} \\\hline V_1 & V_{-i} & h_{uv} & i & i h_{uv} \\\hline V_{-1} & V_1 & h_{uv} & -1 & -h_{uv} \\\hline V_{-1} & V_{-1} & h_{uv} & 1 & h_{uv} \\\hline V_{-1} & V_i & h_{uv} & i & i h_{uv} \\\hline V_{-1} & V_{-i} & h_{uv} & -i & -i h_{uv} \\\hline V_i & V_1 & h_{uv} & -i & -i h_{uv} \\\hline V_i & V_{-1} & h_{uv} & i & i h_{uv} \\\hline V_i & V_i & h_{uv} & 1 & h_{uv} \\\hline V_i & V_{-i} & h_{uv} & -1 & -h_{uv} \\\hline V_{-i} & V_1 & h_{uv} & i & i h_{uv} \\\hline V_{-i} & V_{-1} & h_{uv} & -i & -i h_{uv} \\\hline V_{-i} & V_i & h_{uv} & -1 & -h_{uv} \\\hline V_{-i} & V_{-i} & h_{uv} & 1 & h_{uv} \\ \hline \end{array}\] Each entry in the last column matches the definition of the Hermitian adjacency matrix after four-way switching, confirming \(H(G') = D^{-1} H(G) D\).
Consider the Hermitian permanental polynomial \[\operatorname{per}(xI – H(G')) = \operatorname{per}(xI – D^{-1} H(G) D).\]
Note that \(D^{-1}(xI)D = xI\), so \[xI – H(G') = D^{-1}(xI – H(G))D.\]
Let \(B = xI – H(G)\); we need to prove \(\operatorname{per}(D^{-1} B D) = \operatorname{per}(B)\).
By the definition of the permanent, we have \[\operatorname{per}(D^{-1} B D) = \sum_{\sigma \in S_n} \prod_{k=1}^n [D^{-1} B D]_{k,\sigma(k)}.\]
For any \(\sigma \in S_n\), we have \[[D^{-1} B D]_{k,\sigma(k)} = d_k^{-1} B_{k,\sigma(k)} d_{\sigma(k)}.\]
Decompose \(\sigma\) into disjoint cycles \(c_1 \cdots c_m\). For each cycle \(c = (i_1 \cdots i_r)\), \[\begin{aligned} \prod_{k \in c} [D^{-1} B D]_{k\sigma(k)} &=(d_{i_1}^{-1} B_{i_1 i_2} d_{i_2}) (d_{i_2}^{-1} B_{i_2 i_3} d_{i_3}) \cdots (d_{i_r}^{-1} B_{i_r i_1} d_{i_1}) \\ &= (d_{i_1}^{-1} d_{i_1}) (d_{i_2}^{-1} d_{i_2}) \cdots (d_{i_r}^{-1} d_{i_r}) \cdot B_{i_1 i_2} B_{i_2 i_3} \cdots B_{i_r i_1} \\ &= \prod_{j=1}^r B_{i_j i_{j+1}}, \end{aligned}\] where \(i_{r+1} = i_1\), and \(d_{i_j}^{-1} d_{i_j} = 1\) cancels out in the cycle.
Thus, \[\begin{aligned} \prod_{k=1}^n [D^{-1} B D]_{k,\sigma(k)} = \prod_{k=1}^n B_{k,\sigma(k)}. \end{aligned}\]
Summing over all \(\sigma\) gives \[\begin{aligned} \operatorname{per}(D^{-1} B D) = \operatorname{per}(B). \end{aligned}\]
Therefore, \[\begin{aligned} \operatorname{per}(xI – H(G')) = \operatorname{per}(xI – H(G)). \end{aligned}\] ◻
Example 4.9. Consider the mixed graphs \(G\) and \(G'\) shown in Figures 7 and 8.
Take the admissible partition \(V_1 = \{v_1, v_3, v_4\}\), \(V_{-1} = \{v_2\}\), \(V_i = V_{-i} = \emptyset\). Then \(d_{v_1}=1\), \(d_{v_3}=1\), \(d_{v_4}=1\), \(d_{v_2}=-1\). This partition satisfies conditions (a) and (b) of the four-way switching rule. By operation (c), the single arcs of type \((1,-1)\) and \((-1,1)\) are reversed: \(v_1 \to v_2\) becomes \(v_2 \to v_1\), and \(v_2 \to v_3\) becomes \(v_3 \to v_2\). Edges within \(V_1\) (\(v_3v_4\) and \(v_4v_1\)) are undirected (digons) and remain unchanged. The resulting graph \(G'\) is non-isomorphic to \(G\) (the directions of the two edges are reversed), but by Theorem 4.8, \(G\) and \(G'\) have the same Hermitian permanental polynomial.
This proof shows that the switching equivalence class of \(G\) contains all mixed graphs obtained by performing a single four-way switching on \(G\) or its transpose \(G^T\).
In this section, by computer we enumerate the Hermitian permanental polynomials for all mixed graphs on at most 6 vertices, and we count the numbers of such mixed graphs for which there is another mixed graph with the same Hermitian permanental polynomial.
All mixed graphs on at most 6 vertices were generated using nauty and Traces [6]. The Hermitian permanental polynomials of these mixed graphs were then computed with a Maple procedure. Finally, the numbers of H-copermanental mixed graphs were counted based on the obtained polynomials.
Two mixed graphs \(G_1\) and \(G_2\) are said to be H-copermanental if they have the same Hermitian permanental polynomial (equivalently, the same Hermitian permanental spectrum). A mixed graph \(G\) is said to be determined by its Hermitian permanental polynomial if any mixed graph H-copermanental with \(G\) is isomorphic to \(G\).
| \(n\) | \(\#\) mixed graphs | \(\#\) Hermitian permanental pols | \(\#\) determined | max. family |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2 | 1 | 2 |
| 3 | 16 | 6 | 2 | 6 |
| 4 | 218 | 27 | 3 | 21 |
| 5 | 9,608 | 285 | 5 | 158 |
| 6 | 1,540,944 | 14,596 | 23 | 1,593 |
The results are summarized in Table 1. Table 1 lists, for \(n\le 6\), the total number of mixed graphs on \(n\) vertices, the total number of distinct Hermitian permanental polynomials of such graphs, the number of such graphs determined by the Hermitian permanental polynomial, and the size of the largest family of H-copermanental mixed graphs.
In [3], the total number of distinct Hermitian characteristic polynomials, the total number of mixed graphs determined by the Hermitian characteristic polynomial, and the size of the largest family of H-cospectral mixed graphs are presented for all mixed graphs on at most 6 vertices (see Table 2). From Tables 1 and 2, we see that, among mixed graphs on six vertices, 23 are determined by the Hermitian permanental polynomial, whereas 16 are determined by the Hermitian characteristic polynomial. The Hermitian permanental polynomial appears to be slightly more effective than the Hermitian characteristic polynomial in distinguishing mixed graphs, at least for the cases examined.
| \(n\) | \(\#\) mixed graphs | \(\#\) Hermitian characteristic pols | \(\#\) determined | max. family |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 2 | 1 | 2 |
| 3 | 16 | 6 | 2 | 6 |
| 4 | 218 | 27 | 3 | 21 |
| 5 | 9,608 | 275 | 5 | 158 |
| 6 | 1,540,944 | 10,920 | 16 | 1,338 |
In this paper, we first focus on the basic properties of the permanental polynomial derived from the Hermitian adjacency matrix of mixed graphs, establishing a connection between its coefficients and those of the characteristic polynomial. We then further investigate this polynomial, determining the number of zero permanental roots for several special classes of mixed graphs. Finally, we characterize some families of mixed graphs that share the same permanental spectrum.
All newly generated computational data in this study are presented in Table 2. The data from previous studies used for comparison are available in the cited reference [3].
The authors declare that they have no conflicts of interest.
This study is supported by NSFC (No. 12261071)and NSF of Qinghai Province (No. 2025-ZJ-902T).