EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 15, No. 3, 2022, 841-855 ISSN 1307-5543 – ejpam.com Published by New York Business Global Hermitian Adjacency Matrices of Mixed Graphs Mohammad Abudayah1,∗, Omar Alomari1, Torsten Sander2 1 School of Basic Sciences and Humanities, German Jordanian University, Amman, Jordan 2 Fakultät für Informatik, Ostfalia Hochschule für angewandte Wissenschaften, Wolfenbüttel, Germany Abstract. The traditional adjacency matrix of a mixed graph is not symmetric in general, hence its eigenvalues may be not real. To overcome this obstacle, several authors have recently defined and studied various Hermitian adjacency matrices of digraphs or mixed graphs. In this work we unify previous work and offer a new perspective on the subject by introducing the concept of monographs. Moreover, we consider questions of cospectrality. 2020 Mathematics Subject Classifications: 05C50, 15A18 Key Words and Phrases: Mixed graphs, oriented graphs, graph spectra, eigenvalues, cospec- trality 1. Introduction Algebraic graph theory strives to relate the structural properties of graphs to the algebraic properties of objects associated with them. Specifically, in spectral graph theory the eigenvalues and eigenvectors of matrices associated with graphs are studied. Most traditionally, the object of interest would be the adjacency matrix of some undirected graph, i.e., the square matrix [auv] such that auv = 1 if there is an edge between vertices u and v, otherwise auv = 0. By construction, the adjacency matrix of an undirected graph is symmetric. Hence theorems from linear algebra dealing with non-negative symmetric matrices can be readily applied to obtain a number of desirable spectral properties. Most notably, the spectrum of the adjacency matrix is real. Moreover, there exists a basis of pairwise orthogonal eigenvectors. However, when dealing with directed or mixed graphs the definition of the adjacency matrix needs to be changed to accommodate the fact that the adjacency relation of vertices is no longer symmetric. For a digraph we set auv = 1 if there is an arc from vertex number u to v and auv = 0 otherwise. The loss of symmetry proves a serious impediment to relating algebraic and structural properties to one another, cf. the survey [4]. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v15i3.4448 Email addresses: mohammad.abudayah@gju.edu.jo (M. Abudayah), omar.alomari@gju.edu.jo (O. Alomari), t.sander@ostfalia.de (T. Sander) https://www.ejpam.com 841 © 2022 EJPAM All rights reserved. M. Abudayah, O. Alomari, T. Sander / Eur. J. Pure Appl. Math, 15 (3) (2022), 841-855 842 Quite recently, the idea has been presented to modify the definition of the adjacency matrix of a directed graph, some authors studied the matrix AA∗, see [1, 2], and others used complex numbers, in such a way that it still properly reflects the adjacency relation but at the same time constitutes a Hermitian matrix. Let us give an overview of some efforts and results in this direction. In [5] the authors use the imaginary number i to specify auv = i and avu = −i whenever there is an arc from u to v, but not vice versa, further auv = 1 whenever u and v are mutually adjacent. Using this definition of a Hermitian adjacency matrix, it turns out that many results from algebraic graph theory known for undirected graphs also hold for directed graphs or at least exist in a slightly modified or weaker version. For example, if the underlying undirected graph of a given oriented graph is bipartite, then the spectrum of the Hermitian adjacency matrix is symmetric with respect to zero, but – in contrast to the undirected case – the reverse is not true. Independently, the authors of [10] introduced the same notion of a Hermitian adjacency matrix and proved many fundamental results. Moreover, they considered the Gutman energy (which is the sum of the absolute values of all eigenvalues) of the Hermitian adjacency matrix. Refer to [8, 9, 12] for other related work. The goal of the present paper is as follows. To begin with, we generalize and unify previous results. We will then introduce the concept of monographs, permitting us to view some of these results from a new perspective. Moreover, we will analyze under which conditions a mixed graph has identical spectra for different values of α. 2. Preliminaries All graphs considered hereafter shall not contain any loops or multiple edges. A mixed graph D arises from partially orienting an undirected graph G, i.e. by turning some of the undirected edges into single arcs. Thus, between any two adjacent vertices u, v of the vertex set V (G) there exists either an arc from u to v (indicated by u→v), an arc from v to u (indicated by u←v), or an undirected edge (also called a digon) between u und v (indicated by u∼v). Altogether, these arcs and digons form the edge set E(D) of D. The graph G is called the underlying graph Γ(D) of the mixed graphD. Much of the traditional terminology (e.g. being regular, being connected, vertex degree deg(·), maximum degree ∆) that is used for undirected graphs simply carries over to mixed graphs, in the sense that, D is said to have a property whenever Γ(D) has this property. In particular, we say that a mixed graph contains a certain undirected subgraph (e.g. the path Pk or the cycle Ck on k vertices) if Γ(D) contains this subgraph. A mixed walk in D is a sequence of vertices v1, . . . , vk of D such that there is an edge between any two subsequent vertices vivi+1 in D. The set of all arcs from some vertex u to other vertices v (resp. from other vertices to u) is denoted by N+ D (u) (resp. N− D (u)). The set of all digons incident with vertex u is denoted by ND(u). The (traditional) adjacency matrix A(G) = [aij ] of a given, either undirected or di- rected, graph G on n vertices is the real matrix of order n×n such that aij = 1 if there is an edge from vi to vj and aij = 0 otherwise. For directed graphs, the resulting matrix A is usually non-symmetric, thus losing many desirable algebraic properties. We therefore M. Abudayah, O. Alomari, T. Sander / Eur. J. Pure Appl. Math, 15 (3) (2022), 841-855 843 define the following alternative: Definition 1. Given a mixed graph D and a unit complex number α, i.e. |α| = 1, we define the α-Hermitian adjacency matrix Hα(D) = [huv] of D by huv =  1 if u∼v, α if u→v, ᾱ if u←v, 0 otherwise. (1) When there is no ambiguity regarding the reference graph D we will often omit any symbolic reference to D, e.g. write Hα instead of Hα(D). Clearly, the matrix Hα from Definition 1 is Hermitian, i.e. (Hα)∗ = (Hα) where M∗ denotes the conjugate transpose of matrix M . By χα(D,x) = det(xI−Hα(D)), where I is the identity matrix, we denote the characteristic polynomial of the matrix Hα(D), calling this the α-characteristic polynomial of D. The multiset σα(D) of all roots of χα(D,x) is called the α-spectrum of D, as opposed to the (traditional) spectrum σ(Γ(D)) of the underlying undirected graph Γ(D). Consequently, we shall refer to the elements of σα(D) as the α-eigenvalues of D. Likewise, we speak of α-eigenvectors. Note that α-eigenvalues are always real. A direct consequence of Definition 1 is the following summation rule characterizing α-eigenvectors: Proposition 1. Let D be a mixed graph. Then x is an α-eigenvector of D corresponding to α-eigenvalue λ if and only if, for each u ∈ V (D), λx(u) = ∑ u∼v x(v) + ( α ∑ u→v x(v) ) + ( ᾱ ∑ u←v x(v) ) . (2) Throughout this paper we shall assume |α| = 1, i.e. α = eiθ for some θ ∈ R. Moreover, we make use of the constants ω := e π 3 i (a sixth root of unity) and γ := e 2π 3 i (a third root of unity). In the context of Hermitian adjacency matrices, the former constant has been endorsed in [11], whereas the suitability of the latter constant will become evident later on. 3. Characteristic Polynomial of Hα(D) In this section we will expand the determinant of Hα and study the α-characteristic polynomial, in particular with respect to the three instances H i, Hw and Hγ . A classic result from linear algebra, concerning determinant expansion, is the following: Theorem 1. If A = [ai,j ] is a square matrix of order n then det(A) = ∑ η∈Sn sgn(η)a1,η(1)a2,η(2)a3,η(3) . . . an,η(n). (3) M. Abudayah, O. Alomari, T. Sander / Eur. J. Pure Appl. Math, 15 (3) (2022), 841-855 844 Decades ago, the above theorem has been applied to adjacency matrices of graphs. The permutations over which the sum ranges can be put into correspondence with certain subgraphs of the given graph. To this end, we define the following terms and notation: Definition 2. Let D be a mixed graph. (i) D is called elementary if, for every component C of D, Γ(C) is either isomorphic to P2 or Ck (for some k ≥ 3). (ii) Let D be elementary. The rank of D is defined as r(D) = n−c, where n = |V (D)| and c is the number of its components. The co-rank of D is defined as s(D) = m− r(D), where m = |E(D)|. Note that the co-rank s(D) is equal to the number of Ck components of D. Now we are ready to state the following classic theorem by Harary (cf. [6]): Theorem 2 (Determinant expansion (Harary, 1962)). Let D be a graph with adjacency matrix A(G). Then, det(A(G)) = ∑ S (−1)r(S)2s(S), (4) where the sum ranges over all spanning elementary subgraphs S of G. Following the classic proof strategy used in Theorem 2, the result readily generalizes to any α-Hermitian adjacency matrix. But first we require the following definition: Definition 3. Let D be a mixed graph and Hα(D) = [huv]. With respect to this, the value hα(W ) of a mixed walk W with vertices v1, v2, . . . , vk is defined as hα(W ) = (hv1v2hv2v3hv3v4 · · ·hvk−1vk) ∈ {α r}r∈Z. (5) Theorem 3 (Determinant expansion for Hα). Let D be a mixed graph. Then det(Hα) = ∑ D′ (−1)r(D′) 2s(D ′)Re (∏ C hα(C⃗) ) , (6) where the sum ranges over all spanning elementary mixed subgraphs D′ of D, the product ranges over all mixed cycles C in D′, and C⃗ is any closed walk traversing C. Proof. Consider the matrix Hα and apply the classic proof strategy for determinant expansion on graphs, cf. the proof of Theorem 2 in [3]. Considering specific values of α, the formula in Theorem 3 becomes more specific, too. For α = i we may rediscover a result given in [10]. Moreover, Theorem 3 immediately allows us to compute the α-characteristic polynomial: M. Abudayah, O. Alomari, T. Sander / Eur. J. Pure Appl. Math, 15 (3) (2022), 841-855 845 1 2 3 4 5 Figure 1: A mixed graph where σγ , σω, σi are different from one another Corollary 1. If χα(D,λ) = λn + c1λ n−1 + c2λ n−2 + · · · + cn is the α-characteristic polynomial of a mixed graph D, then (−1)kck = ∑ (−1)r(D′) 2s(D ′)Re (∏ C hα(C⃗) ) , (7) where the sum ranges over all elementary mixed subgraphs D′ with k vertices, the product ranges over all mixed cycles C in D′, and C⃗ is any closed walk traversing C. Proof. This follows immediately from the fact that (−1)kck equals the sum of all principal minors of Hα(D) with k rows and columns. 4. Cospectrality A recurring theme in algebraic graph theory is the hunt for pairs of non-isomorphic graphs having the same spectrum. Such graphs are called cospectral. In contrast to this, we shall look into the question under which conditions the same graph has identical α-spectrum for different values of α. It comes as no surprise that such spectra may be completely different: Example 1. For the mixed graph shown in Figure 1 we have: σγ = {2.57083,−2.3222, 1.50413,−1.19239,−0.560369} σω = {−2.93033, 2.30034, 1.15439,−0.832963, 0.308565} σi = {−2.71687, 2.2803, 1.50739,−1.07082, 0.0} However, there exist mixed graphs exhibiting the same α-spectrum for two different values of α, say α1, α2. We call such a mixed graph α1-α2-cospectral. Let us give an example for a γ-ω-cospectral mixed graph: Example 2. The mixed graph D shown in Figure 2 is γ-ω-cospectral, i.e. σγ(D) = σω(D). This is not difficult to see: with respect to Corollary 1 note that D contains only one cycle. Moreover, hγ(c) ∈ {γ, γ2} and hω(c) ∈ {ω2, ω2}. Observing γ = ω2 we have χγ(D,λ) = χω(D,λ). In contrast, we remark that χα(D,λ) ̸= χi(D,λ), hence σα(D) ̸= σi(D). Note that for α = 1 we have Hα = A(Γ(D)), so the special case of α-1-cospectrality is equivalent to asking whether the α-spectrum of a mixed graph D coincides with the traditional spectrum of its undirected counterpart Γ(D). Thus Corollary 1 immediately gives rise to the following result: M. Abudayah, O. Alomari, T. Sander / Eur. J. Pure Appl. Math, 15 (3) (2022), 841-855 846 1 2 3 4 5 6 7 8 9 10 11 Figure 2: A γ-ω-cospectral mixed graph Corollary 2. Let T be a mixed tree. Then σα(T ) = σ(Γ(T )). Proof. Trees do not contain cycles, hence using α = 1 in (7) instead of the given value does not change the result. Since trees are α-1-cospectral for any α we see that they are α1-α2-cospectral for arbitrary values α1,α2. Now, consider a mixed graph that contains cycles. Obviously, it does not matter for equation (7) if we use α = 1 or some other specific value as long as (with respect to that other value) all factors in the involved products are equal to one. This motivates the following definition: Definition 4. A mixed graph is an α-monograph (of 1st kind) if hα(C⃗) = 1 for all its cycles C. Trivially, trees are α-monographs. By construction, Corollary 2 directly extends to monographs: Theorem 4. Let D be an α-monograph (of 1st kind). Then, σα(D) = σ(Γ(D)). Regarding Corollary 1 and (7), note that hα(C⃗) = αxᾱy = αx−y, where x (resp. y) is the number of forward (resp. backward) edges encounterd while traversing C⃗. We will tacitly make use of this fact hereafter. Corollary 3. Let D be a connected mixed graph. If, for every cycle in D, the difference between the numbers of encountered forward arcs and the number of backward arcs (w.r.t. any traversal direction) is a multiple of the order of α, then D is an α-monograph. Corollary 4. A connected mixed graph G is an α-monograph for every value α if and only if every cycle in D contains as many forward arcs as backward arcs. Proof. For the forward implication note that there exist values α of infinite order (i.e. αj = αk only if j = k). The converse follows directly from Corollary 3. The properties of α-monographs deserve further investigation. But beforehand, we will elaborate more on cospectrality. We start with the question when the α-spectra for the special values γ and ω coincide: M. Abudayah, O. Alomari, T. Sander / Eur. J. Pure Appl. Math, 15 (3) (2022), 841-855 847 Theorem 5. Let D be a mixed graph. If, for any cycle in D, the difference between the numbers of encountered forward arcs and the number of backward arcs (w.r.t. any traversal direction) is even, then D is γ-ω-cospectral. Proof. Under the given assumptions there will be only even powers of α in (7). But Re(γ2k) = Re(ω2k). Corollary 5. Let D be a mixed bipartite graph. Suppose that every cycle in D contains an even number of digons. Then D is γ-ω-cospectral. Proof. A bipartite graph contains only even cycles. Consider such a cycle C. Sub- tracting an even number of digons, we conclude that C contains an even number of arcs. Traversing C, these arcs either consist of an even number of forward arcs and an even number of backward arcs or consist of an odd number of forward arcs and an odd number of backward arcs. Hence Theorem 5 can be applied. Corollary 6. Every oriented bipartite graph is γ-ω-cospectral. As already mentioned in Example 2, the graph in Figure 2 is γ-ω-cospectral. This follows from Corollary 6 since it is an oriented bipartite graph. Using the ideas from the proof of Corollary 5, one can generalize as follows: Theorem 6. Let D be a mixed graph. Suppose that every even cycle in D contains an even number of digons and every odd cycle in D contains an odd number of digons. Then D is γ-ω-cospectral. We have shown how Corollary 1 can be used as a tool investigating cospectrality. In view of α1-α2-cospectrality it is sufficient to require that, for every elementary mixed subgraph D′, the real part of the associated product in (7) is the same for both values α1 and α2. As a slightly coarser condition one could require that hα1(C⃗) = hα2(C⃗) for all cycles C of D′. In view of this, requiring uniform cospectrality for all values of α1,α2 (hence including value 1) amounts to the condition hα(C⃗) = 1 stated in Definition 4. In view of this, one can devise modifications which, given some α-monograph D, can be used to construct arbitrarily many derived α-monographs containing D as a subgraph: Theorem 7. Let D be an α-monograph. Let U be a connected undirected subgraph of D. Fix a set M of new vertices and subsets Vx ⊂ V (U), for x ∈ M . Connect each vertex x ∈M to Vx such that either N+ D (x) = Vx or N− D (x) = Vx. Then the resulting mixed graph D̃ is an α-monograph. Proof. The newly added vertices and their adjacent edges may introduce new cycles. Let C be such a cycle in D̃ and C⃗ any traversal of C. By construction, the predecessor vx of x and its successor wx (w.r.t. C⃗) belong to U . Consider the residual graph R obtained by removing all edges of U from D. Every path W in R joining two vertices u1, u2 that originally belong to the subgraph U in D satisfies hα(W ) = 1. To see this, add any path W ′ between u1 and u2 in U to obtain a cycle CW inD. Choosing matching traversals forW M. Abudayah, O. Alomari, T. Sander / Eur. J. Pure Appl. Math, 15 (3) (2022), 841-855 848 1 2 3 4 5 6 7 12 8 9 10 11 13 Figure 3: Extending an α-monograph and W ′, we get hα(C⃗W ) = hα(W⃗ )hα(W⃗ ′). Observe hα(W⃗ ′) = 1 since U is an undirected subgraph of D. D is an α-monograph, so hα(C⃗W ) = 1 and therefore hα(W⃗ ) = 1. C can be segmented into paths of three possible types as follows: Paths within U , paths within R and the segment from vx via x to wx. The latter segment can only be vx→x←wx or vx←x→wx. Both contribute a factor of 1 to the product hα(C⃗), as do the two segment types mentioned first. Overall, hα(C⃗) = 1. Example 3. Figure 3 illustrates the construction mentioned in Theorem 7. The vertices no. 12 und 13 have been newly added. 5. Monograph Structure Definition 4 characterizes α-monographs by a condition concerning the traversal of cycles. In the following, we will render the implications of this condition more tangible, by way of studing mixed walks. To this end, let D be a connected mixed graph. Fix any u ∈ V (D) and consider some mixed walk W in D, say u = r1, . . . , rk. Denote the contained partial walks r1, . . . , rj by Wj (for j = 1, . . . , k). Consequently, hα(W1) = 1 (8) and hα(Wj+1) =  hα(Wj) if rj∼rj+1 αhα(Wj) if rj→rj+1 ᾱhα(Wj) if rj←rj+1 (9) for j = 1, . . . , k − 1. M. Abudayah, O. Alomari, T. Sander / Eur. J. Pure Appl. Math, 15 (3) (2022), 841-855 849 1 2 3 γ 4 1 5 1 1 6 1 7 γ (a) Walk from/to vertex no. 5 1 γ 2 1 3 1 γ 4 γ2 5 1 6 7 γ2 (b) Walk from/to vertex no. 3 1 γ2 2 γ 3 γ γ2 4 1 5 1 γ 6 7 (c) Another walk from/to vertex no. 5 Figure 4: Values of hγ(Wj) for three closed mixed walks W Example 4. Figure 4 shows the values hγ(Wj) – each value written near the respective j-th vertex along the walk – for three different mixed walks W in a mixed graph. Next, we state three useful basic properties of hγ with respect to mixed walks (some of which already implicit in the previous section). Proposition 2. Let W be a mixed walk containing r forward arcs and s backward arcs. Then hα(W ) = αrᾱs. Proposition 3. Let W ′ be a mixed walk and W ′′ the corresponding reverse walk. Let W be the walk resulting from concatenating W ′ and W ′′. Then hα(W ) = 1. Proposition 4. Let W ′,W ′′ be two mixed walks such that the final vertex of W ′ is the start vertex of W ′′. Let W be the walk resulting from concatenating W ′ and W ′′. Then hα(W ) = hα(W ′)hα(W ′′). As can be seen from Figure 4, hα can be used to assign (possibly multiple) complex numbers to each of the vertices of a mixed graph. In particular, we are concerned about the possible values that get assigned to the start/end vertices of closed walks: Definition 5. Let D be a mixed graph. The α-store Sα(u) of u ∈ V (D) is defined as Sα(u) = {hα(W ) : W is a closed walk in D from/to u}. Let sα(u) = |Sα(u)| denote the associated store size. M. Abudayah, O. Alomari, T. Sander / Eur. J. Pure Appl. Math, 15 (3) (2022), 841-855 850 1 2 3 γ 4 1 5 1 1 6 1 7 γ (a) Walk #1 from/to vertex no. 5 1 γ2 2 γ 3 γ γ 4 1 1 5 1 1 6 1 7 γ (b) Walk #2 from/to vertex no. 5 Figure 5: Values of hγ(Wj) for two closed walks in a γ-monograph Trivially, 1 ∈ Sα(u) and so sα(u) ≥ 1. As the following lemma shows, the store content is independent of u, hence we may speak of ‘the’ α-store of a mixed graph: Lemma 1. Let u, v ∈ V (D). Then Sα(u) = Sα(v). Proof. Let W ′′ be a closed mixed walk from/to v. Clearly, hα(W ′′) ∈ Sα(v). Now let W ′ be a mixed walk from u to v and let W ′′′ its reverse walk. Concatenating W ′, W ′′, W ′′′ one obtains a closed mixed walk W from/to v. Using Proposition 3 and Proposition 4 we get hα(W ) = hα(W ′)hα(W ′′)hα(W ′′′) = hα(W ′′), so that hα(W ′′) ∈ Sα(u). Repeating the argument with the roles of u and v swapped yields Sα(v) = Sα(u). Theorem 8. Let D be a connected mixed graph. Then the following statements are equiv- alent: (i) sα(u) = 1 for at least one u ∈ V (D). (ii) sα(u) = 1 for every u ∈ V (D). (iii) hα(W ′) = hα(W ′′) for every pair W ′,W ′′ of mixed walks sharing the same start and end vertices. (iv) D is an α-monograph (of 1st kind). Proof. Observing Definition 4 and Definition 5, this follows from Proposition 3, Propo- sition 4 and Lemma 1. Example 5. The mixed graph shown in Figure 4 is not a γ-monograph, as opposed to the slightly different graph depicted in Figure 5. Notice how, in view of Theorem 8, every mixed walk with the same start/end vertex creates exactly the same walk values along the way. In view of Theorem 8, one can characterize α-monographs by the way their vertices can be partitioned: M. Abudayah, O. Alomari, T. Sander / Eur. J. Pure Appl. Math, 15 (3) (2022), 841-855 851 Theorem 9. A connected mixed graph D is an α-monograph (of 1st kind) if and only if V (D) can be partitioned into sets Vα0 , Vα1 , Vα2 , . . . (some of which possibly empty) such that there are no digons between any two sets Vαj1 , Vαj2 with j1 ̸= j2 and every arc starting in a set Vαj ends in Vαj−1. Proof. Given an α-monograph D, use Theorem 8 (iii) as follows. Fix any vertex u ∈ V (D) and assign each vertex v ∈ V (D) to the set Vαj , where αj = hα(W ) for an arbitrary walk from u to v. Conversely, consider a mixed graph with a vertex partition as supposed. We may assume V0 ̸= ∅. Fix any v ∈ V0. Considering some vertex w ∈ Vαk and an arbitrary mixed walk W from v to w, we see that the partition structure aligns with (8) and (9), so that inductively we conclude αk = hα(W ). Thus, condition (iii) of Theorem 8 is satisfied. Furthermore, the store values of an α-monograph D permit us to convert the eigen- vectors of Γ(D) into eigenvectors of D: Theorem 10. Let D be an α-monograph and x = [xu]u∈V (D) an eigenvector of Γ(D) for eigenvalue λ. Fixing a reference vertex v ∈ V (D), define the vector y = [yr]r∈V (D) = [hα(v⇝r)xr]r∈V (D) , (10) where v⇝r is an arbitrary mixed walk from v to r in D (cf. Theorem 8 (iii)). Then y is an α-eigenvector of D for eigenvalue λ. Proof. Clearly, for every vertex u, the vector x satisfies the summation rule λxu = ∑ r∈NΓ(D)(u) xr. (11) Using the recursion (9) as well as equations (10) and (11), we deduce: λyu = λhα(v⇝u)xu (12) = ∑ r∈NΓ(D)(u) hα(v⇝u)xr (13) = ∑ r∈ND(u) hα(v⇝u)xr + ∑ r∈N+ D(u) hα(v⇝u)xr + ∑ r∈N− D (u) hα(v⇝u)xr (14) = ∑ r∈ND(u) hα(v⇝r)xr + α ∑ r∈N+ D(u) hα(v⇝r)xr + ᾱ ∑ r∈N− D (u) hα(v⇝r)xr (15) = ∑ r∈ND(u) yr + α ∑ r∈N+ D(u) yr + ᾱ ∑ r∈N− D (u) yr. (16) Comparing this to the mixed summation rule (2) from Proposition 1, we see that y is as claimed. Regarding Theorem 10, note that the construction (10) retains linear independence, i.e., every basis of eigenvectors of Γ(D) can be converted into a basis of α-eigenvectors of D (using the same reference vertex v throughout). M. Abudayah, O. Alomari, T. Sander / Eur. J. Pure Appl. Math, 15 (3) (2022), 841-855 852 1 −i 2 −1 31 1 4 i Figure 6: An i-monograph of 2nd kind Example 6. Figure 5b depicts an α-monograph D. With respect to the indicated ver- tex order, (−1,−1, 1, 1, 0,−1, 1)T is an eigenvector of Γ(D) for eigenvalue 0. Using equation (10) and the store values given in the figure, one obtains the γ-eigenvector (−γ,−γ2, γ2, 1, 0,−1, γ2)T for eigenvalue 0 of D. In preparation for the following section we define a variant of the function hα. As before, let D be a connected mixed graph. Fix u ∈ V (D) and let W be a mixed walk u = r1, . . . , rk in D. Slightly changing equations (8) and (9), we define gα(Wj) = (−1)j+1hα(Wj), (17) for j = 1, . . . , k. The properties mentioned in Propositions 2 to 4 also hold for gα(W ), thus justifying an alternative notion of α-store. Using this notion and the following definition instead of Definition 4, one can check that Lemma 1 and Theorem 8 remain valid for gα(W ) as well. Definition 6. A mixed graph is an α-monograph (of 2nd kind) if gα(C⃗) = 1 for all its cycles C. As a result, we can derive results analogous to (but slightly different from) Theorem 9 and Theorem 4: Theorem 11. A connected mixed graph D is an α-monograph (of 2nd kind) if and only if V (D) can be partitioned into sets . . . , V−α2 , V−α1 , V−α0 , Vα0 , Vα1 , Vα2 , . . . (some of which possibly empty) such that digons occur only between pairs of sets Vαj , V−αj and any arc starting in a set Vαj ends in Vαj−1. Theorem 12. Let D be an α-monograph (of 2nd kind). Then, σα(D) = −σ(Γ(D)). Example 7. The mixed graph D shown in Figure 6 is an i-monograph of 2nd kind. We have σi(D) = {−3, 1(3)} and σ(Γ(D)) = {3,−1(3)}. Clearly, D is not an i-monograph of 1st kind. 6. Spectral Radius The spectral radius ρ(M) of a complex matrix M is defined as the largest modulus among its eigenvalues. If ∥·∥ is any matrix norm, we have ρ(M) ≤ ∥M∥ (cf. Theorem 5.6.9 M. Abudayah, O. Alomari, T. Sander / Eur. J. Pure Appl. Math, 15 (3) (2022), 841-855 853 in [7]). Using the maximum norm ∥ ·∥∞, one immediately obtains the classic upper bound ρ(G) ≤ ∆G on the spectral radius ρ(G) := ρ(A(G)) of an undirected graph G. Supposing G is connected, equality holds if and only if G is regular. Considering a mixed graph D and its α-Hermitian adjacency matrix Hα(D) instead, it follows from Definition 1 that ∥Hα(D)∥∞ = ∥A(Γ(D))∥∞, since all nonzero entries of Hα(D) have modulus 1. Hence, ρα(D) ≤ ∆Γ(D). Interestingly, α-monographs come into play if one wants to characterize when equality holds: Theorem 13. Let D be a connected mixed graph. Then, ρα(D) = ∆Γ(D) if and only if D is a regular α-monograph (of 1st or 2nd kind). Proof. Let x = [xu]u∈V (D) be an α-eigenvector of D for α-eigenvalue λ. Choose v ∈ V (D) such that |xv| is maximal. We may assume |xv| = 1. Using Proposition 1, we can deduce that |λ| = |λxv| ≤ ∑ u∈N(v) |xu|+ ∑ u∈N+(v) |αxu|+ ∑ u∈N−(v) |αxu| (18) = ∑ u∈N(v) |xu|+ ∑ u∈N+(v) |xu|+ ∑ u∈N−(v) |xu| (19) ≤ ∑ u∈N(v) |xv|+ ∑ u∈N+(v) |xv|+ ∑ u∈N−(v) |xv| (20) = degΓ(D)(v) (21) ≤ ∆Γ(D). (22) Suppose that λ is an α-eigenvalue of D with largest modulus. The condition ρα(D) = ∆Γ(D) holds if and only if equality holds in all three conditions (18), (20) and (22). Equality in (22) is achieved if any only if D (resp. Γ(D)) is regular of degree ∆Γ(D). Since |xv| is maximal, equality in (20) occurs exactly if |xu| = |xv| = 1 for all u ∈ NΓ(D)(v). Repeat this argument for all vertices u ∈ NΓ(D), each time taking the role of v. Since Γ(D) is connected, we successively prove |xu| = 1 for all u ∈ V (D). Equality holds in the complex triangle inequality (18) if and only if arg(λxv) = arg(xu) for all u ∈ NΓ(D)(v). In the following, we shall skip the trivial case λ = 0 = ρα(D). Let arg(α) = θ ∈ R. Consider the following cases: (i) Case λ > 0: • If u ∈ N(v), then arg(xu) = arg(λxv), so that xu = xv. • If u ∈ N+(v), then arg(αxu) = arg(λxv), so that xu = ᾱxv. • If u ∈ N−(v), then arg(ᾱxu) = arg(λxv), so that xu = αxv. Assigning each vertex u ∈ V (D) to a set Vθ with θ = xu/xv, we obtain a partition as mentioned in Theorem 9. REFERENCES 854 (ii) Case λ < 0: • If u ∈ N(v), then arg(xu) = arg(λxv), so that xu = −xv. • If u ∈ N+(v), then arg(αxu) = arg(λxv), so that xu = −ᾱxv. • If u ∈ N−(v), then arg(ᾱxu) = arg(λxv), so that xu = −αxv. Assigning each vertex u ∈ V (D) to a set Vθ with θ = xu/xv, we obtain a partition as mentioned in Theorem 11. Conversely, let D be a connected mixed graph having a vertex partition according to one of the cases (i) or (ii). Construct a vector x = [xu]u∈V (D) as follows. Set xu := q for any u ∈ Vq. It is straightforward to show that x is an α-eigenvector for an eigenvalue of modulus ρα(D). Corollary 7. Let D be a connected mixed graph. Suppose that αk ̸= −αl for all k, l ∈ Z. Then, ρα(D) = ∆Γ(D) if and only if D is a regular α-monograph of 1st kind. Proof. The given condition on α guarantees that the partition arising in case (ii) in the proof of Theorem 13 can be converted into a bipartition V (D) = V ′∪̇V ′′, with V ′ = Vα0 ∪ Vα1 ∪ . . . and V ′′ = V−α0 ∪ V−α1 ∪ . . ., such that the subgraphs induced by V ′ and V ′′ have no edges. So D would be bipartite in this case. Forming pairwise unions Vαk ∪ V−αk , it becomes apparent that D must be an α-monograph of 1st kind. To conclude, let us briefly revisit the three special choices i, ω and γ for α. Choosing α = γ, the conditions of Corollary 7 are met, but not for α ∈ {i, ω}. In view of this, γ appears to be an interesting choice for α. Moreover, since γ is a third root of unity, among all candidates satisfying the conditions of Corollary 7, choosing α = γ will yields a minimal number of sets in the monograph vertex partition. References [1] Mohammad Abudayah, Omar Alomari, and Torsten Sander. On the n-spectrum of oriented graphs. Open Mathematics, 18(1):486–495, 2020. [2] Omar Alomari, Mohammad Abudayah, and Torsten Sander. The non-negative spec- trum of a digraph. Open Mathematics, 18(1):22–35, 2020. [3] Norman Biggs. Algebraic graph theory. Cambridge University Press, 2nd ed. edition, 1994. [4] Richard A. Brualdi. Spectra of digraphs. Linear Algebra Appl., 432(9):2181–2213, 2010. [5] Krystal Guo and Bojan Mohar. Hermitian adjacency matrix of digraphs and mixed graphs. J. Graph Theory, 85(1):217–248, 2017. REFERENCES 855 [6] Frank Harary. The determinant of the adjacency matrix of a graph. SIAM Rev., 4:202–210, 1962. [7] Roger A. Horn and Charles R. Johnson. Matrix analysis. Reprinted with corrections. Cambridge University Press, 1990. [8] Irena M. Jovanović. Non-negative spectrum of a digraph. Ars Math. Contemp., 12(1):167–182, 2017. [9] Honghai Li and Teng Yu. Hermitian adjacency spectrum of Cayley digraphs over dihedral group. Algebra Colloq., 27(1):121–130, 2020. [10] Jianxi Liu and Xueliang Li. Hermitian-adjacency matrices and Hermitian energies of mixed graphs. Linear Algebra Appl., 466:182–207, 2015. [11] Bojan Mohar. A new kind of Hermitian matrices for digraphs. Linear Algebra Appl., 584:343–352, 2020. [12] Bo-Jun Yuan, Yi Wang, Shi-Cai Gong, and Yun Qiao. On mixed graphs whose Hermitian spectral radii are at most 2. Graphs Comb., 36(5):1573–1584, 2020.